問題一覧 > 通常問題

No.1582 Vertexes vs Edges

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 79
作問者 : magstamagsta / テスター : butsurizukibutsurizuki
4 ProblemId : 5739 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-19 18:21:53

問題文

$N$ 個の頂点の木が与えられます。木の頂点には $1$ から $N$ までの、辺には $N-1$ までの番号が付けられています。

辺 $i$ は頂点 $u_i, v_i$ を結んでいます。最初全ての頂点は白で塗られています。


A 君と B 君が、この木を用いてゲームを行います。

A 君は下記の A 君の操作、B 君は下記の B 君の操作 をそれぞれ行います。また、これらの操作を両者は交互に行います。先手は A 君です。

A 君の操作
繋いでいる頂点 2 つが両方とも白で塗られている辺を 1 つ選び、両方の頂点を黒で塗る。

B 君の操作
黒で塗られている頂点を 1 つ選び、その頂点を白で塗る。

A 君が操作できなくなるとき (A 君が操作しようとするときに、繋いでいる頂点 2 つ両方が白で塗られている辺が存在しないとき) まで、これらの操作を交互に繰り返します。


A 君は最終的に黒で塗られた頂点を出来るだけ多くしようとし、 B 君は最終的に白で塗られた頂点を出来るだけ多くしようとします。

最終的に黒で塗られている頂点はいくつあるかを求めてください。

入力

$N$
$u_1\ \ v_1$
$u_2\ \ v_2$
$:$
$u_{N-1}\ \ v_{N-1}$

  • $2 \leq N \leq 10^5$
  • $1 \leq u_i, v_i \leq N$
  • $u_i \neq v_i$
  • 入力は全て整数である
  • 入力が表すグラフは木である

出力

求めた値を出力し、最後に改行せよ。

サンプル

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

まず、最初の A 君の操作で、頂点 1 とそれ以外の頂点 1 つが必ず黒で塗られます。

次の B 君の操作で、頂点 1 ではない方の黒で塗られた頂点を白で塗ります。

こうすると、A 君は操作できなくなり、最終的に黒で塗られている頂点の数は 1 つとなります。


また、B 君の操作で頂点 1 以外を白く塗ってしまうと、最終的に黒で塗られている頂点の数は 2 つ以上になってしまいます。

よって、求める答えは 1 といえます。

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

サンプル3
入力
12
1 7
8 2
3 12
6 7
7 11
9 1
4 10
12 2
10 1
1 2
5 10
出力
5

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