刷题记录:牛客NC24263[USACO 2018 Feb G]Directory Traversal
传送门:牛客
题目描述:
题目较长,此处省略
输入:
8
bessie 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0
输出:
42
感觉是一道较难的二次扫描换根dp的题目
主要思路:
- 首先分析一下我们的题目,我们会发现当前的节点uuu如果往下走到节点vvv的话,那么消耗的数值为v文件的name+1v文件的name+1v文件的name+1,但是从v节点往上走到uuu节点的话消耗的是../../../,也就是333点消费.然后题目的要求就是求出一个文件夹节点,使其到任意其他叶子节点的距离和最小(注意此处我们的文件夹节点默认是有文件的)
- 然后根据树形dp的套路,我们应该不难想到使用f[u]来记录所有uuu的子树中的叶子节点,并且应该有一个显然的转移想法,当前的uuu节点的距离和应该是所有子节点的距离和,也就是∑fv\sum_{}^{}{f_v}∑fv,并且在这个的基础上还需要加上当前结点往下走一步的贡献(这个贡献与我们的v节点的长度有关,我们可以先进行预处理,存在w[u][v]中).然后就不难得出我们的dp方程了:
f[u]+=leaf_size[v]∗w[u][i]+f[v];f[u]+=leaf\_size[v]*w[u][i]+f[v];f[u]+=leaf_size[v]∗w[u][i]+f[v];
leaf_size存储的是当前v节点的所有叶子节点的个数leaf\_size存储的是当前v节点的所有叶子节点的个数leaf_size存储的是当前v节点的所有叶子节点的个数
- 但是显然的,我们现在存储的只是每一个节点的儿字的贡献,但是事实上我们的路径之和还包括我们的父亲对其的贡献.这就需要我们使用换根dp换根dp换根dp的想法了
- 我们再使用一个数组g[u]g[u]g[u]来存储我们父亲那边的贡献.这个贡献由两部分组成:
1.一部分是我们当前结点的兄弟结点的贡献
2.一部分是我们的当前结点的父亲的父亲的那边的贡献
对于第一部分来说,我们考虑一下我们的文件路径的移动方式,对于我们的兄弟结点中的每一个叶子结点,我们都是需要我们的当前的节点往上移动一步,然后再往下移动到各个节点.这一部分的总贡献就是:3∗(leaf_size[u]−leaf_size[v])+f[u]−f[v]−w[u][v]∗leaf_size[v]3*(leaf\_size[u]-leaf\_size[v])+f[u]-f[v]-w[u][v]*leaf\_size[v]3∗(leaf_size[u]−leaf_size[v])+f[u]−f[v]−w[u][v]∗leaf_size[v],注意这一部分我们还需要减去我们的刚开始由uuu节点往下走到v节点,因为我们的f[v]f[v]f[v]并没有包括这一部分
对于我们的第二部分来说,我们发现需要求出的父亲的父亲的贡献其实在我们的dfs过程中就可以求出来了,为g[u]g[u]g[u].但是类似的,我们还需要加上我们的当前节点v走到节点u的贡献.也就是3∗(leaf_size[1]−leaf_size[u])3*(leaf\_size[1]-leaf\_size[u])3∗(leaf_size[1]−leaf_size[u])
对于最终的答案,就是在所有的f[u]+g[u]−leaf_size[1]f[u]+g[u]-leaf\_size[1]f[u]+g[u]−leaf_size[1]中取最小值即可,为什么要减一呢,这是因为我们在之前求路径的时候将每一个叶子节点也多加了一个$$符号,所以我们需要在答案过程中减去每一个叶子节点的多余贡献
下面是具体的代码部分:
#include
#include
#include
#include
#include
#include