USACO 2018 February Contest, Gold

Problem 2. Directory Traversal


Contest has ended.

Log in to allow submissions in analysis mode


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.

INPUT FORMAT (file dirtraverse.in):

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 FORMAT (file dirtraverse.out):

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.

SAMPLE INPUT:

8
bessie 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0

SAMPLE OUTPUT:

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

Problem credits: Mark Gordon

Contest has ended. No further submissions allowed.