在某大型企业的内部资料库中，所有文件被分门别类地存放在若干层文件夹中。整个资料库有一个根目录（root），从该目录包含若干子文件夹与文件。每个文件夹下又可以继续包含文件或其他文件夹，从而形成一棵树形的层级结构。

例如：

root/
  folder1/
    file1
    folder2/
      file2
  folder3/
    file3
  file4

该文件结构表示：

• 在根目录 root 下有 folder1、folder3 两个文件夹，以及一个 file4 文件。
• 在 folder1 文件夹中有一个 file1 文件，以及 folder2 文件夹，folder2 文件夹中有一个 file2 文件。
• 在 folder3 文件夹中有一个 file3 文件。

当你位于某个文件夹中时，你可以通过相对路径，来访问到任何你想要访问的文件。

从一个文件夹到某个文件的相对路径是：从当前文件夹出发，使用 ../ 表示返回上一级文件夹，用 / 连接子文件夹，直到到达目标文件。

相对路径长度指的是：路径中所有字符的总数（包括斜杠 / 与点号 .）。

比如，假设你位于 root 文件夹：

• 访问 file1，相对路径为：folder1/file1，相对路径长度为 13。
• 访问 file2，相对路径为：folder1/folder2/file2，相对路径长度为 21。
• 访问 file3，相对路径为：folder3/file3，相对路径长度为 13。
• 访问 file4，相对路径为：file4，相对路径长度为 5。

再比如，假设你位于 folder1 文件夹：

• 访问 file1，相对路径为：file1，相对路径长度为 5。
• 访问 file2，相对路径为：folder2/file2，相对路径长度为 13。
• 访问 file3，相对路径为：../folder3/file3（注意这里需要先从 folder1 文件夹中通过 ../ 返回 root，才能访问到 folder3），相对路径长度为 16。
• 访问 file4，相对路径为：../file4，相对路径长度为 8。

企业希望设置一个默认打开位置（即选择一个文件夹作为入口），使得从这个文件夹出发，访问所有文件所需的相对路径长度总和最小。

第一行输入一个整数 N，表示所有文件和文件夹的总数。

接下来 N 行描述各个文件或文件夹的信息。

每一行的格式为：

name m id1 id2 ... idm

其中：

• name 表示文件或文件夹的名称，仅由小写字母和数字组成。
• 如果 m = 0，表示这是一个文件。
• 如果 m > 0，表示这是一个文件夹，其中包含 m 个子项（这些子项的编号依次为 id1, id2, ..., idm）。

文件/文件夹的编号从 1 到 N，其中 1 号一定是根目录（即 root）。

输出一个整数，表示最小的相对路径长度总和。

样例 1 说明

该样例对应的目录结构即题目描述中的结构：

root/
  folder1/
    file1
    folder2/
      file2
  folder3/
    file3
  file4

将默认打开位置设在 folder1 中，可以使得所有文件访问所需的相对路径长度总和最小。

所有文件访问相对路径长度总和为：5+13+16+8=42。（具体相对路径，请参考题目描述）

数据范围

对于 10\% 的数据，满足 N \leq 10。

对于 20\% 的数据，满足 N \leq 200。

对于 30\% 的数据，满足 N \leq 3500。

对于 100\% 的数据，满足 2 \le N \leq 10^5，0 \le m \lt N，文件/文件夹的名称长度不超过 16 个字符。

月赛树形DP换根DP25年11月