問題一覧 > 通常問題

No.1718 Random Squirrel

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 36
作問者 : nok0nok0 / テスター : zkouzkou Kite_kumaKite_kuma 👑 ygussanyygussany
2 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$ にリスが出現した場合のリスの移動回数を求めてください。

制約

  • 入力は全て整数である。
  • $2 \le N \le 10^5$
  • $1 \le K \le N$
  • 与えられるグラフは木である。
  • $1 \le D_1 < D_2 < \dots < D_K \le N$

入力

$N$ $K$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
$D_1$ $D_2$ $\dots$ $D_K$

出力

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

サンプル

サンプル1
入力
3 1
1 2
2 3
1
出力
0
1
2

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

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

サンプル2
入力
5 4
1 2
1 3
1 4
1 5
2 3 4 5
出力
7
6
6
6
6

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