ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

8079: Directory Traversal

内存限制：128 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：5 通过：3
提交提交记录统计Web Board

题目描述

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≤N≤100,0002≤N≤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 NN, where ID 1 refers to the top level directory. Next, there will be NN 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, mm. If mm is 0, then this entity is a file. If m>0m>0, then this entity is a directory, and it has a total of mm files or directories inside it. Following mm there will be mm 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

输入格式

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

输入样例 复制 

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

分类标签