시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB96231622.857%

문제

그대는 내 머리 위의 우산, 어깨 위에 차가운 비 내리는 밤, 내 곁에 그대가 없는 반쪽의 세상, 그댄 나 없이는 안 돼요.

- <우산>, 윤하

윤하는 트리 구조를 한 도시에 살고 있다. 도시에는 비가 오고 있다. 도시의 정점은 N개로, 1번부터 N번까지 번호가 붙어 있다.

윤하는 방문하고 싶은 K개의 서로 다른 정점들을 골랐다. 윤하는 지금 1번 정점에 있다. 각 간선이 잇는 두 정점 사이를 이동하는 데에는 1초의 시간이 걸린다. 윤하는 K개의 정점들 중 몇 개를 지금 방문하려 한다. K개의 정점들 중 1개, 2개, …, K개를 방문하는 데 필요한 최소의 시간을 계산해 주자.

하나의 정점을 여러 번 방문할 때에는 첫 번째 방문만 셈한다는 것, 그리고 정점들을 방문한 뒤에 윤하가 1번 정점에 다시 돌아올 필요가 없다는 것에 유의하자.

입력

첫 줄에 정점의 개수 N과 윤하가 방문하고 싶은 정점의 개수 K가 주어진다. (1 ≤ N ≤ 300,000, 1 ≤ K ≤ 5,000, K < N)

둘째 줄부터 N-1개의 줄에는 윤하가 사는 도시의 간선들이 잇는 정점들의 번호를 나타내는 두 정수 ai와 bi가 주어진다. (1 ≤ ai, bi ≤ N, ai ≠ bi)

마지막 줄에는 윤하가 방문하고 싶은 정점들의 번호를 나타내는 서로 다른 K개의 정수 c1, ..., cK가 공백을 사이에 두고 주어진다. (ci ≠ 1)

출력

윤하가 방문하고 싶은 정점들 중 1개, 2개, …, K개를 방문하기 위해 필요한 최소 시간을 공백을 사이에 두고 순서대로 출력하라.

예제 입력 1

4 3
1 2
1 3
3 4
2 3 4

예제 출력 1

1
2
4
  • 정점 1에서 출발해서 1의 시간에 방문하고 싶은 정점 2, 3, 4 중 하나를 방문하는 경로에는 1 → 2가 있다. 더 짧은 경로는 없다.
  • 정점 1에서 출발해서 2의 시간에 방문하고 싶은 정점 2, 3, 4 중 둘을 방문하는 경로에는 1 → 3 → 4가 있다. 더 짧은 경로는 없다.
  • 정점 1에서 출발해서 4의 시간에 방문하고 싶은 정점 2, 3, 4 중 셋(모두)을 방문하는 경로에는 1 → 2 → 1 → 3 → 4가 있다. 더 짧은 경로는 없다.

예제 입력 2

10 4
10 4
4 6
5 1
4 3
2 3
2 8
9 3
7 2
2 1
4 8 9 10

예제 출력 2

2
4
6
8

출처

Contest > 웰노운컵 > 제2회 웰노운컵 Day 1 C번

  • 데이터를 추가한 사람: jh05013
  • 문제를 만든 사람: junie