시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1665 | 939 | 751 | 55.961% |
한동이는 경상도내를 돌아다니면서 열심히 일하는 영업사원이다. 예전에는 자기가 원하는 도시만 골라서 다닐 수 있었지만 시대가 바뀌어서 이제 그렇게는 하지 못하게 되었다. 시대가 바뀜에 따라, 한동이는 회사에서 돌아야 할 도시의 목록을 받고, 그 목록대로 도시를 여행한다. 회사에서 주는 여행지 목록은 정말 안타깝게도 최적화되어 있지가 않다. 여행을 떠나기 전에 한동이는 모든 도시를 방문하는데 걸리는 최소의 시간을 알고싶어하는데, 한동이는 경영학과라 컴퓨터를 하지 못 하기 때문에 여러분이 한동이를 도와주자.
포항 시내의 도시들은 1부터 n까지 번호 지어져 있다. 한동이는 항상 포항시청에서 여행을 시작하고, 포항시청의 번호는 항상 1번이다. 모든 도시들은 양방향 도로로 연결되어있는데 한 도시에서 바로 길이 이어져있는 다른 도시로 이동하는데는 항상 1의 시간이 걸린다. 포항시청에서는 어떤 도시든지 갈 수 있다. 또한 포항의 도로는 굉장히 잘 되어있어서 도로끼리 사이클을 만들지 않는다.
여러분의 목표는 한동이가 모든 도시를 방문하는데 걸리는 최소의 시간을 출력하는 것이다.
입력의 첫 줄에는 포항에 있는 도시의 숫자 n이 주어진다. 1 ≤ n ≤ 30,000.
다음 n-1줄에는 도시를 잇는 도로가 주어진다. 각 줄에는 정수 a와 b가 주어진다. 이는 a도시와 b도시를 잇는 도로가 존재한다는 의미이다. (1 ≤ a,b ≤ n; a≠b)
n+1번째 줄에는 정수 m이 주어지는데, 이는 한동이가 방문해야 할 도시의 숫자를 의미한다. 1 ≤ m ≤ 5,000 그 후 m개의 줄에는 한 줄에 하나씩 한동이가 방문해야 할 도시의 숫자가 순서대로 주어진다.
첫 줄에 한동이가 방문해야 할 모든 도시를 방문 할 수 있는 최소 시간을 출력한다.
5 1 2 1 5 3 5 4 5 4 1 3 2 5
7
Olympiad > Polish Olympiad in Informatics > POI 2001/2002 > Stage 1 2번