問題一覧 > 通常問題

No.1718 Random Squirrel

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 52
作問者 : nok0 / テスター : zkou Kite_kuma ygussany
お気に入りにしたユーザー ProblemId : 6569 / 自分の提出
問題文最終更新日: 2021-10-16 18:45:10
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 319 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。