問題一覧 > 通常問題

No.277 根掘り葉掘り

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 150
作問者 : koyumeishikoyumeishi
4 ProblemId : 666 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:43

問題文

$N$頂点の木が一つ与えられる。
各頂点には$1$~$N$の番号が重複なく割り当てられていて、頂点$1$がこの木の根である。
ある頂点$i$について、根からの距離を$R_i$、一番近い葉からの距離を$L_i$とする。
頂点番号順に$min(R_i, L_i)$を出力せよ。

注) 頂点$u$から頂点$v$に移動するときに通る最小の辺の数を、頂点$u$から頂点$v$への距離(頂点$v$から頂点$u$への距離)とする。

入力

$N$
$x_1$ $y_1$
$\vdots$
$x_{N-1}$ $y_{N-1}$

1行目には頂点数$N$が与えられる。
2行目以降$N-1$行に辺の情報が空白区切りで与えられる。$i$番目の辺は頂点$x_i$と$y_i$を結ぶ辺である。
入力は全て整数で、以下の制約を満たす。
$ 2 \leq N \leq 10^5$
$ 1 \leq x_i < y_i \leq N$
$ i \neq j $ のとき $ x_i \neq x_j $ または $ y_i \neq y_j $ であることが保証される。 つまり多重辺や自己ループはなく、木は連結である。

出力

$min(R_1, L_1)$
$\vdots$
$min(R_N, L_N)$

$i$行目に$min(R_i, L_i)$を出力せよ。

サンプル

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

$R_i$を青、$L_i$を赤で示す。

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

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