/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 150 点
問題文
platypusくんは，射的の景品で N 頂点からなる連結な無向木をもらいました． このままでは持ち運びにくいので，木を一つのパスにしたいと思いました． (パスとは，すべての頂点の次数が高々2の木のことです) platypusくんは以下の操作で木をパスにします．
- 頂点を好きなだけ追加する
- 木の頂点と1.で追加した頂点との間に，好きなだけ無向辺を加える (木の頂点同士，また1.で追加した頂点同士を辺で結ぶことはできない)
- 2.でできたグラフから，閉路がなくなるまで好きなだけ辺を削除していき，一つの連結なパスにする
以上の操作で，platypusくんは1.で追加する頂点をなるべく少なくしたいと思いました． 与えられた木を上記の操作でパスにするための最小の頂点追加数を求めるプログラムを作りなさい．
制約
すべてのテストケースは以下の制約を満たします．
- 2 \leq N \leq 200000
- 1 \leq u_{i},v_{i} \leq N (1 \leq i \leq N-1)
- 与えられるグラフは木である．
入力
入力は以下の形式で標準入力から与えられる．
N
u_{1} v_{1}
u_{2} v_{2}
:
u_{N-1} v_{N-1}
- 1行目には整数 N が書かれている．これは，platypusくんが入手したグラフの頂点数を表している．
- 続く N-1 行のうち i 行目には二つの整数 u_{i} と v_{i} が空白区切りで書かれている．これは，グラフの i 番目の辺は頂点 u_{i} とv_{i} を結んでいることを表している．
出力
標準出力に，与えられたグラフをパスにするための最小の頂点追加数を一行で出力しなさい．
入力例 1
7 1 2 3 7 4 2 1 3 5 2 3 6
出力例 1
2
2 つの頂点を追加すればよいです． 追加した頂点を X ,Y と呼ぶと， X と 4 ， X と 5 ， Y と 5 ， Y と 6 を辺で結び，最後に 2 と 5 ， 3 と 6 を結ぶ辺をそれぞれ消すと， 6 - Y - 5 - X - 4 - 2 - 1 - 3 - 7というひとつながりのパスが残ります． 1 つの頂点追加のみでこのグラフをパスにすることはできないので，求める答えは 2 です．
入力例 2
5 1 3 3 2 2 5 5 4
出力例 2
0
与えられたグラフはすでにパスのため，答えは 0 です．
入力例 3
9 3 5 4 6 4 2 5 9 8 5 1 2 7 4 3 1
出力例 3
2