No.1718 Random Squirrel

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 52
作問者 :

nok0 / テスター :

zkou

Kite_kuma 👑

ygussany

4 ProblemId : 6569 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-10-16 18:45:10

$N$ 頂点からなる木が与えられます。

頂点には $1$ から $N$ の、辺には $1$ から $N - 1$ の番号がついており、辺 $i$ は頂点 $u_{i}$ と $v_{i}$ を双方向に結んでいます。

与えられる木のうち頂点 $D_{1}, D_{2}, \dots, D_{K}$ にはドングリが置いてあります。

さて、木のランダムな頂点上にリスが出現します。リスはドングリが置いてある頂点を全て訪れるまで以下の方法で移動を繰り返します。

リスはとても賢いので、移動回数が最小になるように移動を行います。

$X = 1, 2, \dots, N$ について、頂点 $X$ にリスが出現した場合のリスの移動回数を求めてください。

 $N$   $K$ 
 $u_{1}$   $v_{1}$ 
 $u_{2}$   $v_{2}$ 
 $⋮$ 
 $u_{N - 1}$   $v_{N - 1}$ 
 $D_{1}$   $D_{2}$   $\dots$   $D_{K}$

$i (1 \leq i \leq N)$ 行目に $X = i$ のときの答えを出力してください。

0
1
2

リスは頂点 $1$ に訪れるために、頂点 $2$ に出現した場合は $1$ 回、頂点 $3$ に出現した場合は $2$ 回の移動を行います。

頂点 $1$ に出現した場合は、出現時点で頂点 $1$ を訪れているために移動する必要はありません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。