Bessie the cow is surprisingly computer savvy. On her computer in the barn, she
stores all of her precious files in a collection of directories; for example:

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

There is a single "top level" directory, called bessie.

Bessie can navigate to be inside any directory she wants. From a given
directory, any file can be referenced by a "relative path". In a relative path,
the symbol ".." refers to the parent directory. If Bessie were in folder2, she
could refer to the four files as follows:

../file1
file2
../../folder3/file3
../../file4

Bessie would like to choose a directory from which the sum of the lengths of the
relative paths to all the files is minimized.

Problem credits: Mark Gordon

Problem credits: Mark Gordon

The first line contains an integer N (\(2 \leq N \leq 100,000\)), giving the total
number of files and directories. For the purposes of input, each object (file
or directory) is assigned a unique integer ID between 1 and \(N\), where ID 1
refers to the top level directory.

Next, there will be \(N\) lines. Each line starts with the name of a file or
directory. The name will have only lower case characters a-z and digits 0-9, and
will be at most 16 characters long. Following the name is an integer, \(m\). If
\(m\) is 0, then this entity is a file. If \(m > 0\), then this entity is a
directory, and it has a total of \(m\) files or directories inside it. Following \(m\)
there will be \(m\) integers giving the IDs of the entities in this directory.

Output the minimal possible total length of all relative paths to files. Note
that this value may be too large to fit into a 32-bit integer.

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > February > Gold