AT_arc179_d [ARC179D] Portable Gate

[problemUrl]: https://atcoder.jp/contests/arc179/tasks/arc179_d 頂点 $ 1,2,\dots\ ,N $ の $ N $ 頂点からなる木が与えられます. $ i $ 番目の辺は頂点 $ u_i,v_i $ を双方向に結んでいます. すべての頂点ははじめ白に塗られています. この木のすべての頂点を効率よく訪れるべく, Alice は不思議なゲートを発明しました. Alice は駒とゲートを $ 1 $ 個ずつ用いて次の手順で旅をします. まず好きな頂点を選び, 駒とゲートをその頂点に置きます. その後, すべての頂点が黒に塗られるまで次の操作を何度も行います. - 次のうち $ 1 $ つを選んで実行する. 1. 駒が置かれている頂点を黒に塗る. 2. 駒が置かれている頂点に隣接した頂点をひとつ選び, その頂点に駒を移動させる, コストが $ 1 $ かかる. 3. ゲートが置かれている頂点に駒を移動させる. 4. 駒が置かれている頂点にゲートを移動させる. コストがかかるのは $ 2 $ 番目の操作のみであることに注意してください. 有限回の操作ですべての頂点を黒に塗ることができることが証明できます. かかるコストの合計の最小値を求めてください.

入力は以下の形式で標準入力から与えられる. > $ N $ $ u_1 $ $ v_1 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

答えを出力せよ.

### 制約 - $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ u_i,v_i\ \leq\ N $ - 与えられるグラフは木である. - 入力される値はすべて整数. ### Sample Explanation 1 Alice の手順の一例を示します. 駒が頂点 $ u $ にありゲートが頂点 $ v $ にある状態を $ (u,v) $ と表すことにします. - 頂点 $ 4 $ に駒とゲートを置く. - 状態は $ (4,4) $ となる. - 操作 $ 1 $ を行う. - 頂点 $ 4 $ が黒く塗られる. - 状態は $ (4,4) $ となる. - 操作 $ 2 $ を行い, 駒を頂点 $ 1 $ に移動させる. - コストが $ 1 $ かかる. - 状態は $ (1,4) $ となる. - 操作 $ 1 $ を行う. - 頂点 $ 1 $ が黒く塗られる. - 操作 $ 4 $ を行う. - 状態は $ (1,1) $ となる. - 操作 $ 2 $ を行い, 駒を頂点 $ 2 $ に移動させる. - コストが $ 1 $ かかる. - 状態は $ (2,1) $ となる. - 操作 $ 1 $ を行う. - 頂点 $ 2 $ が黒く塗られる. - 操作 $ 3 $ を行う. - 状態は $ (1,1) $ となる. - 操作 $ 2 $ を行い, 駒を頂点 $ 3 $ に移動させる. - コストが $ 1 $ かかる. - 状態は $ (3,1) $ となる. - 操作 $ 1 $ を行う. - 頂点 $ 3 $ が黒く塗られる. - すべての頂点が黒く塗られたので, 操作を終了する. 操作 $ 2 $ を行った回数は $ 3 $ なので, かかるコストの合計は $ 3 $ となります. $ 3 $ より小さいコストの手順は存在しません.