No.994 ばらばらコイン

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 227
作問者 : ganmodokixganmodokix / テスター : monkukui2monkukui2
10 ProblemId : 3106 / 出題時の順位表
問題文最終更新日: 2020-02-21 21:32:33

問題文

$N$頂点の無向木を考えます。この木は頂点に$1,2,\cdots,N$の番号が割り振られています。 $N-1$本の辺について、$i$本目の辺の端点は頂点$a_i$と頂点$b_i$です。

始めに、コインが頂点$1$に$K$枚置かれています。
この状態から、 「1枚以上コインの置かれている頂点をひとつ選び、その頂点に置かれているコインのうち1枚以上好きなだけ選んで隣接している頂点に移動する」 という操作を好きなだけ行って、全ての頂点について高々1枚のコインが置かれている状態にしたいです。

この状態にすることが可能であれば、最小で何回の操作が必要か求めてください。

入力

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

制約

  • 入力はすべて整数である。
  • $2\le N\le 10^5$
  • $1\le K\le 10^5$
  • $1\le a_i,b_i \le N$
  • $i\ne j$ならば$(a_i,b_i)\ne(a_j,b_j)$
  • 入力から与えられるグラフは木である。

出力

所定の状態にすることが可能なら最小の操作回数を、不可能なら '-1' を出力し、最後に改行してください。

サンプル

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

頂点$1$に置いてあった$2$枚のコインのうち、$1$枚を頂点$2$に移動させると、最小回数の$1$で所定の状態を達成できます。

サンプル2
入力
5 6
1 2
1 3
1 4
2 5
出力
-1

どのように操作を行っても、いずれかの頂点に$2$枚以上のコインが置かれてしまいます。

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

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