시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (언어별 추가 시간 없음) 1024 MB 26 11 7 38.889%

문제

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

- <우산>, 윤하

머리 위의 우산 같던 그와 헤어진 윤하. 유난히 쌀쌀했던 가을날 비를 맞으며 조용히 걸어가고 있던 윤하는 갑자기 그가 그리워진다. 눈물이 난다. 그의 얼굴을 한 번만 더 보고, 마지막 한 마디를 전하고 싶다는 일념에, 윤하는 그가 있을 만한 곳들로 가 보려 한다. 하지만 발목에 고인 빗물 위 눈물까지 흘리며 걸어가기에 윤하는 자신이 너무나 우습게 느껴저 서러웠다. 그래서 윤하는 지금 그가 있을 수 있는 위치들에 한 곳씩 최대한 빨리 가 보기로 마음을 먹었다.

그와 윤하는 트리 구조를 한 도시에 살고 있다. 도시의 정점은 N개로, 1번부터 N번까지 번호가 붙어 있다. 윤하는 그가 있을 가능성이 있는 K개의 정점들을 골랐다. 윤하는 현재 1번 정점에 있다. 각 간선이 잇는 두 정점 사이를 이동하는 데에는 1초의 시간이 걸린다. 윤하는 그가 있을 가능성이 있는 K개의 정점들 중 몇 개라도 지금 방문하려 한다. K개의 정점들 중 1, …, K개를 방문하는 데 필요한 최소의 시간을 더 이상 비가 거세지기 전에 계산해 주자.

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

입력

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

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

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

출력

윤하가 방문하고 싶은 정점들 중 1, …, 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번

  • 문제를 만든 사람: junie