Umbrella
Time limit2sMemory limit1024 MB
Given a tree rooted at vertex 1, find for each i the minimum walk from vertex 1 that visits i of the K marked vertices.
- Level
Medium7 of 10
- Topics
- Tree, Dynamic programming, DFS
- Solved
- No attempts yet
Problem
그대는 내 머리 위의 우산, 어깨 위에 차가운 비 내리는 밤, 내 곁에 그대가 없는 반쪽의 세상, 그댄 나 없이는 안 돼요.
- <우산>, 윤하
Yunha lives in a city with a tree structure. It is raining in the city. The city has N vertices, numbered from 1 to N.
Yunha has picked K distinct vertices she wants to visit. She is currently at vertex 1. Moving along an edge between two vertices takes 1 second. Yunha will visit some of the K vertices now. Compute the minimum time needed to visit 1, 2, ..., K of the K vertices.
If a vertex is visited several times, only the first visit counts. After visiting the vertices, Yunha does not need to return to vertex 1.
Input
The first line contains N, the number of vertices, and K, the number of vertices Yunha wants to visit (1 ≤ N ≤ 300,000, 1 ≤ K ≤ 5,000, K < N).
Each of the next N-1 lines contains two integers ai and bi, the vertices joined by an edge (1 ≤ ai, bi ≤ N, ai ≠ bi).
The last line contains K distinct integers c1, ..., cK, the vertices Yunha wants to visit (ci ≠ 1).
Output
Print the minimum time needed to visit 1, 2, ..., K of the K vertices, in order, separated by spaces.