/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 700 点
問題文
頂点 1,2,\dots ,N の N 頂点からなる木が与えられます. i 番目の辺は頂点 u_i,v_i を双方向に結んでいます.
すべての頂点ははじめ白に塗られています.
この木のすべての頂点を効率よく訪れるべく, Alice は不思議なゲートを発明しました. Alice は駒とゲートを 1 個ずつ用いて次の手順で旅をします.
まず好きな頂点を選び, 駒とゲートをその頂点に置きます. その後, すべての頂点が黒に塗られるまで次の操作を何度も行います.
- 次のうち 1 つを選んで実行する.
- 駒が置かれている頂点を黒に塗る.
- 駒が置かれている頂点に隣接した頂点をひとつ選び, その頂点に駒を移動させる, コストが 1 かかる.
- ゲートが置かれている頂点に駒を移動させる.
- 駒が置かれている頂点にゲートを移動させる.
コストがかかるのは 2 番目の操作のみであることに注意してください.
有限回の操作ですべての頂点を黒に塗ることができることが証明できます. かかるコストの合計の最小値を求めてください.
制約
- 2 \leq N \leq 2\times 10^5
- 1 \leq u_i,v_i \leq N
- 与えられるグラフは木である.
- 入力される値はすべて整数.
入力
入力は以下の形式で標準入力から与えられる.
N
u_1 v_1
\vdots
u_{N-1} v_{N-1}
出力
答えを出力せよ.
入力例 1
4 1 2 1 3 1 4
出力例 1
3
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 より小さいコストの手順は存在しません.
入力例 2
10 1 7 7 10 10 8 8 3 8 4 10 9 9 6 9 5 7 2
出力例 2
10
Score : 700 points
Problem Statement
You are given a tree with N vertices numbered 1, 2, \dots, N. The i-th edge connects vertices u_i and v_i bidirectionally.
Initially, all vertices are painted white.
To efficiently visit all vertices of this tree, Alice has invented a magical gate. She uses one piece and one gate to travel according to the following procedure.
First, she chooses a vertex and places both the piece and the gate on that vertex. Then, she repeatedly performs the following operations until all vertices are painted black.
- Choose one of the following actions:
- Paint the vertex where the piece is placed black.
- Choose a vertex adjacent to the vertex where the piece is placed and move the piece to that vertex. The cost of this action is 1.
- Move the piece to the vertex where the gate is placed.
- Move the gate to the vertex where the piece is placed.
Note that only the second action incurs a cost.
It can be proved that it is possible to paint all vertices black in a finite number of operations. Find the minimum total cost required.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N
- The given graph is a tree.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
u_1 v_1
\vdots
u_{N-1} v_{N-1}
Output
Print the answer.
Sample Input 1
4 1 2 1 3 1 4
Sample Output 1
3
Here is an example of Alice's procedure. Let (u, v) denote the state where the piece is at vertex u and the gate is at vertex v.
- Place the piece and the gate at vertex 4.
- The state is now (4, 4).
- Perform action 1.
- Vertex 4 is painted black.
- The state is now (4, 4).
- Perform action 2 and move the piece to vertex 1.
- This costs 1.
- The state is now (1, 4).
- Perform action 1.
- Vertex 1 is painted black.
- Perform action 4.
- The state is now (1, 1).
- Perform action 2 and move the piece to vertex 2.
- This costs 1.
- The state is now (2, 1).
- Perform action 1.
- Vertex 2 is painted black.
- Perform action 3.
- The state is now (1, 1).
- Perform action 2 and move the piece to vertex 3.
- This costs 1.
- The state is now (3, 1).
- Perform action 1.
- Vertex 3 is painted black.
- All vertices are now painted black, so the procedure ends.
The total cost of performing action 2 is 3, and there is no procedure with a smaller cost.
Sample Input 2
10 1 7 7 10 10 8 8 3 8 4 10 9 9 6 9 5 7 2
Sample Output 2
10