問題一覧 > 通常問題

No.277 根掘り葉掘り

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

問題文

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

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

入力

N
x1 y1

xN1 yN1

1行目には頂点数Nが与えられる。
2行目以降N1行に辺の情報が空白区切りで与えられる。i番目の辺は頂点xiyiを結ぶ辺である。
入力は全て整数で、以下の制約を満たす。
2N105
1xi<yiN
ij のとき xixj または yiyj であることが保証される。 つまり多重辺や自己ループはなく、木は連結である。

出力

min(R1,L1)

min(RN,LN)

i行目にmin(Ri,Li)を出力せよ。

サンプル

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

Riを青、Liを赤で示す。

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

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