【题目描述】

奶牛 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