問題一覧 > 通常問題

No.1484 木に数を書き込む問題 / Just Write Numbers! 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 38
作問者 : first_vilfirst_vil / テスター : platinumplatinum
4 ProblemId : 6265 / 自分の提出
問題文最終更新日: 2021-04-19 01:00:19

問題文

N 頂点からなる木があります。i 番目の辺は頂点 Ai と頂点 Bi を結んでいます。 この木の各頂点に 1 以上 N 以下の整数を 1 つずつ重複なく書き込むことを考えます。

ある書き込みのスコアは i=1N1dist(i,i+1) と定義されます。 ここで dist(x,y)x が書き込まれた頂点と y が書き込まれた頂点の距離です。

スコアの最小値を求めてください。

入力

N
A1 B1
A2 B2

AN1 BN1
  • 入力はすべて整数
  • 2N2×105
  • 1Ai<BiN
  • 与えられるグラフは木

出力

スコアの最小値を出力し、最後に改行してください。

サンプル

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

例えば各頂点に頂点番号と同じ整数を書き込むとスコアは 4 になります。

サンプル2
入力
5
1 2
2 3
3 4
4 5
出力
4
サンプル3
入力
18
5 17
5 13
2 5
8 13
2 4
5 6
3 17
8 15
6 18
12 13
2 10
2 11
2 16
1 17
7 11
4 9
13 14
出力
28

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