005 - Company Location
時間制限 1 秒 / メモリ制限 64 MB / 得点 20 / x 1 /
問題
K君は株式会社HOJ・コーポレーションを立ち上げることにしました。
本社を置こうと考えている都市$HOJ$は$N$個の街から成っており、すべての街に従業員が一人住んでいます。
$time(i)$を街$i$に本社を置いた時、最も遠くに住む従業員が通勤にかかる時間とします。
$time(i)$を最大化するように$i$を選んだときの$time(i)$を求めてください。
ただし、通勤にかかる時間とは本社の街まで最短経路で移動したときにかかる時間のことで、道路以外の移動にかかる時間は無視できます。
都市$HOJ$の構造は以下の通りです。
$N$個の街と$N-1$本の道路でできていて、すべての街同士は通る道路をうまく選ぶことで互いに行き来できる。
街$i$と街$j$が道路でつながっている場合街$i$から街$j$までは10分で移動できる。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_{N-1}$ $B_{N-1}$
$A_i$,$B_i$は街$A_i$と街$B_i$が道路でつながっていることを示しています。
出力
改行区切りで出力してください。
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $2 \leq N \leq 10^{5}$
- $1 \leq A_i,B_i \leq N$
- $A_i \ne B_i(1 \leq i \leq N)$
- 入力はすべて整数
入出力例
入力例1
3 1 2 1 3
出力例1
20
街$1$に本社を置いた場合、街$2,3$に住んでいる人が最も遠いです。
街$2$に本社を置いた場合、街$3$に住んでいる人が最も遠いです。
街$3$に本社を置いた場合、街$2$に住んでいる人が最も遠いです。
入力例2
5 4 3 1 5 2 1 4 1
出力例2
30