Directory Traversal

题目描述

奶牛 Bessie 出奇地擅长计算机。在她牛棚里的电脑上，她把所有珍贵的文件存放在一组目录中；例如： bessie/ folder1/ file1 folder2/ file2 folder3/ file3 file4 只有一个“顶层”目录，名为 bessie。

Bessie 可以进入任意她想在其中的目录。从某个目录出发，任何文件都可以用一个“相对路径”来引用。在相对路径中，符号 ".." 表示父目录。如果 Bessie 在 folder2 中，她可以如下引用这四个文件： ../file1 file2 ../../folder3/file3 ../../file4

Bessie 想选择一个目录，使得到所有文件的相对路径长度之和最小。

输入格式

第一行包含一个整数 N ($2 \leq N \leq 100,000$)，表示文件和目录的总数。为了便于输入，每个对象（文件或目录）被分配一个从 1 到 $N$ 的唯一整数 ID，其中 ID 1 表示顶层目录。

接下来有 $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

题目鸣谢：Mark Gordon

标签: USACO|2018|Gold

来源

USACO|2018|Gold