Informatica Online Judge

  폴더 순회(Gold) [2184 / 0888]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 5   Total Tried : 5


The Champion of this Problem (C++) : gs16103 - 0ms / 1098byte
My Best Submission (C++) : N/A

[USACO 2018(Mark Gordon)]

Background

젖소 베시는 젖소임에도 불구하고 컴퓨터를 잘 다룬다. 헛간에 있는 베시의 컴퓨터에는 폴더가 다음과 같이 잘 정리되어 있다.
bessie/
folder1/
file1
folder2/
file2
folder3/
file3
file4


그리고, 최상위 폴더의 이름은 "bessie" 이다.

베시는 어떤 위치에서 시작하던지, "상대경로" 방법으로 모든 파일을 참조할 수 있다. 상대경로에서 기호 ".."는 상위 폴더를 의미한다.

만약 베시가 "folder2"에 있다면 4개의 파일에 다음과 같이 접근할 수 있다.
../file1
file2
../../folder3/file3
../../file4


베시는 모든 파일에 접근하기 위해 필요한 상대경로의 길이가 최소인 폴더를 선택하고 싶어한다.

Input

첫 번째 줄에는 자연수 N이 입력된다. 이 값은 모든 파일과 폴더의 개수를 나타낸다.

입력을 위해 각 파일 또는 폴더에는 1부터 N까지의 고유 ID 번호가 정수로 부여된다. ID 1은 최상위 폴더를 의미한다.

다음으로 N개의 줄이 입력된다. 각 줄은 파일이나 폴더 이름으로 시작된다. 파일이나 폴더의 이름은 알파벳 소문자와 숫자로 구성되며 최대 길이는 16자이다.

이름 다음에는 정수 m이 입력된다. 이 값은 하위 오브젝트(파일이나 폴더)의 개수를 의미한다. 정수 값 m이 0이면 파일을 의미한다.

그 다음에는 m개의 (파일 또는 폴더의) ID가 공백으로 구분되어 입력된다.

[입력값의 정의역]
$2≤N≤100,000$

Output

모든 각각의 파일에 접근하는 상대경로를 출력한다고 할 때, 필요한 문자의 최소 개수를 출력한다.

IO Example

입력
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

*설명 : folder1에 위치하면 다음과 같은 상대경로 방법으로 모든 파일에 접근할수 있으며, 모든 파일에 접근하는데 필요한 문자의 길이는 42가 된다.

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

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]