#PU814. USACO 2018 February Contest, Gold — Problem 2. Directory Traversal

    ID: 1381 传统题 文件IO:dirtraverse 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb18来源:usaco.orgscoring:equal_test_cases树形DP枚举

USACO 2018 February Contest, Gold — Problem 2. Directory Traversal

USACO 2018 February Contest, Gold — Problem 2. Directory Traversal

题目描述

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.

输入格式

The first line contains an integer N (2≤N≤100,0002 \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 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.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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
Problem credits: Mark Gordon

提示

that this value may be too large to fit into a 32-bit integer.