2907. [USACO Feb18] 目录遍历

【题目描述】

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

bessie/

    folder1/

        file1

    folder2/

        file2

    folder3/

        file3

    file4

只有一个“顶层”的文件夹，叫做 bessie。

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

../file1

file2

../../folder3/file3

../../file4

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

【输入格式】

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

【输出格式】

输出所有文件的相对路径的长度之和的最小值。注意这个值可能超过 $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

【来源】

USACO 2018 February Gold Directory Traversal

供题：Mark Gordon