[ARC179D] Portable Gate

题面翻译

给定一颗 $n$ 个点的树，你要给所有点染色。你有一个门和一个棋子。一开始，你要选择一个节点开始并把门和棋子放在这个节点上。然后你可以不断做以下的操作：

1. 把棋子所在节点染色
2. 把棋子移动到其所在节点的其中一个相邻节点
3. 把棋子移动到门所在的节点
4. 把门移动到棋子所在的节点

求最少使用多少次第二个操作才能将所有点染色。

题目描述

頂点 $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}$

输出格式

答えを出力せよ.

样例 #1

样例输入 #1

4
1 2
1 3
1 4

样例输出 #1

3

样例 #2

样例输入 #2

10
1 7
7 10
10 8
8 3
8 4
10 9
9 6
9 5
7 2

样例输出 #2

10

提示

制約

• $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$ より小さいコストの手順は存在しません.