【考题·动态规划】[USACO2018]Directory Traversal（二次扫描·树形DP）

题目描述

奶牛Bessie令人惊讶地精通计算机。她在牛棚的电脑里用一组文件夹储存了她所有珍贵的文件，比如：

bessie/
folder1/
file1
folder2/
file2
folder3/
file3
file4
只有一个“顶层”的文件夹，叫做bessie。

Bessie可以浏览任何一个她想要访问的文件夹。从一个给定的文件夹，每一个文件都可以通过一个“相对路径”被引用。在一个相对路径中，符号“…”指的是上级目录。如果Bessie在folder2中，她可以按下列路径引用这四个文件：

…/file1
file2
…/…/folder3/file3
…/…/file4
Bessie想要选择一个文件夹，使得从该文件夹出发，对所有文件的相对路径的长度之和最小。

输入格式（文件名：dirtraverse.in）：
第一行包含一个整数N（2≤N≤100,0002≤N≤100,000），为所有文件和文件夹的总数量。为了便于输入，每个对象（文件或文件夹）被赋予一个唯一的1至NN之间的ID，其中ID 1指的是顶层文件夹。
接下来有NN行。每行的第一项是一个文件或是文件夹的名称。名称仅包含小写字母a-z和数字0-9，长度至多为16个字符。名称之后是一个整数mm。如果mm为0，则该对象是一个文件。如果m>0m>0，则该对象是一个文件夹，并且该文件夹下共有mm个文件或文件夹。在mm之后有mm个整数，为该文件夹下的对象的ID。

输出格式（文件名：dirtraverse.out）：
输出所有文件的相对路径的长度之和的最小值。注意这个值可能超过32位整数的表示范围。
输入样例：
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
这个输入样例描述了上面给出的样例目录结构。

最优解是选择folder1。从这个文件夹出发，相对路径分别为：

file1
folder2/file2
…/folder3/file3
…/file4
供题：Mark Gordon

题解

好吧以前从来没有遇见过这样的题，考试的时候也没来得及打暴力；个人认为这道题的难度还是有的，可能有的处理上比较套路，但是在字符串这些关系上面还是比较复杂的、而且审题十分重要。

按照文件的排列方式可以看出这是一个树的数据结构，因此：这道题的算法就是两遍树形DP，如果我们$f[i]$表示以$i$为根的答案，那么第一次就是求出$f[1],$而第二次则是根据每一个点与点之间的相对关系来求出每一个$f$值，这样我们就可以在最后直接比较答案即可。

第一次DP的过程中，我们需要求出$sz[i]$表示以i为根节点时包含多少个叶子节点，$dis[i]$表示根节点到第$i$个节点时，需要多少个字符；显然，对于当前节点$x$，若$y\in son(x)$且 x x