問題一覧 > 通常問題

No.806 木を道に

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 341
作問者 : sinsincoscossinsincoscos / テスター : keymoonkeymoon
17 ProblemId : 2507 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-03-22 21:06:30

問題文

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

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。