페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4061

Directory Traversal 2s 512MB

문제

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


입력

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.


예제 

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

This input describes the example directory structure given above.

The best solution is to be in folder1. From this directory, the relative paths are:

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

출처

USACO 2018 February Gold

로그인해야 코드를 작성할 수 있어요.