問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 20
作問者 : ir_1st_vilir_1st_vil / テスター : platinumplatinum
1 ProblemId : 6265
問題文最終更新日: 2021-04-19 01:00:19

問題文

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

ある書き込みのスコアは $\displaystyle \sum_{i=1}^{N-1}\mathrm{dist}(i,i+1)$ と定義されます。 ここで $\mathrm{dist}(x,y)$ は $x$ が書き込まれた頂点と $y$ が書き込まれた頂点の距離です。

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

入力

$N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_{N-1}\ B_{N-1}$
  • 入力はすべて整数
  • $2 \le N \le 2 \times 10^5$
  • $1 \le A_i \lt B_i \le N$
  • 与えられるグラフは木

出力

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

サンプル

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。