No.806 木を道に

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 220
作問者 : sinsincoscossinsincoscos / テスター : keymoonkeymoon
14 ProblemId : 2507 / 出題時の順位表

問題文

umgくんは,$N$頂点の無向木を持っています。$i$番目の辺は,頂点$a_i$と$b_i$を結んでおり,辺$(a_i,b_i)$と書くことにします。彼は次の操作を行うことができます。
操作:異なる3つの頂点$u,v,w$を選び,辺$(u,v)$を辺$(u,w)$に変更する。
umgくんは,この操作を何回か行って,持っている木を道にしたいです。道とは,次数が1である頂点が2つのみであるような無向木のことを指します。
umgくんが目的を達成するのに必要な最小の操作の回数を求めてください。

入力

$N$
$a_1\ b_1$
$\vdots$
$a_{N-1}\ b_{N-1}$

$3\le N \le 10^5$
$1\le a_i , b_i \le N$
与えられるグラフは木である。
$i\neq j$のとき,$(a_i,b_i)\neq (a_j,b_j)$である。

出力

答えを1行に出力してください。最後に改行してください。

サンプル

サンプル1
入力
4
1 2
1 3
1 4
出力
1

辺$(2,1)$を辺$(2,4)$に変えることで目的を達成できます。

サンプル2
入力
3
1 2
2 3
出力
0

最初から道になっているので,操作をする必要はありません。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。