No.1718 Random Squirrel
Problem Statement
You are given a tree with $N$ vertices.
The vertices are numbered from $1$ to $N$ and the edges are numbered from $1$ to $N-1$. Edge $i$ bidirectionally connects vertices $u_i$ and $v_i$.
In the given tree, acorns are placed on vertices $D_1,D_2,\dots,D_K$.
Now, a squirrel appears on a random vertex of the tree. The squirrel repeats the following move until it has visited all the vertices on which acorns are placed.
- Move to a vertex connected by an edge to the vertex where the squirrel currently is.
The squirrel is very clever, so it moves in such a way that the number of moves is minimized.
For each $X=1,2,\dots,N$, find the number of moves the squirrel makes if it appears on vertex $X$.
Constraints
- All inputs are integers.
- $2 \le N \le 10^5$
- $1 \le K \le N$
- The given graph is a tree.
- $1 \le D_1 < D_2 < \dots < D_K \le N$
Input
$N$ $K$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
$D_1$ $D_2$ $\dots$ $D_K$
Output
On the $i\ (1\le i \le N)$-th line, output the answer for $X=i$.
Sample
Sample 1
Input
3 1 1 2 2 3 1
Output
0 1 2
To visit vertex $1$, the squirrel makes $1$ move if it appears on vertex $2$, and $2$ moves if it appears on vertex $3$.
If it appears on vertex $1$, it has already visited vertex $1$ at the moment it appears, so it does not need to move.
Sample 2
Input
5 4 1 2 1 3 1 4 1 5 2 3 4 5
Output
7 6 6 6 6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
nok0
Kite_kuma