Informatica Online Judge

  입시설명회 [2395 / 095B]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 9   Total Tried : 10


The Champion of this Problem (C++) : gs17044 - ms / 1172byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

G 대학교는 전국에서 입시 설명회를 개최한다.

입시 담당자는 돌아야 하는 도시의 목록을 받고 그 목록대로 입시설명회를 돌아다녀야 된다.

입시 담당자는 모든 도시를 방문하는데 걸리는 최소의 일수를 알고싶다.

입시 설명회를 하는 도시들은 1부터 N으로, 처음 시작은 항상 대학교에서 시작하므로 대학교가 1번이다.

모든 도시들은 양방향 도로로 연결되어 있는데 한 도시에서 바로 연결된 다른 도시까지는 항상 하루가 걸린다.

대학교에서는 어떤 도시든지 갈 수 있고, 도로끼리는 사이클이 존재하지 않는다.

입시 담당자가 모든 도시를 방문하는데 걸리는 최소의 일수를 출력해주자.

Input

첫번째 줄에는 방문해야 되는 도시의 숫자 $N$이 주어진다. $(1 <= N <= 30,000)$ 

다음 N-1줄에는 도시를 연결하는 도로 정수 $a$와 $b$가 주어진다. $ (1 <= a, b <= N, a!=b)$

그 다음으로는 입시 담당자가 방문해야 할 도시의 수 $M$이 주어진다. $( 1 <= M <= 5,000)$  

M개의 줄에는 입시 담당자가 방문해야 하는 도시의 숫자가 순서대로 주어진다.

Output

입시 담당자가 모든 도시를 방문하는데 걸리는 최소의 일수를 출력한다.

IO Example

입력
5
1 2
1 5
3 5
4 5
4
1
3
2
5

출력
7

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