G - Vertex Deletion Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点の木が与えられます。頂点には 1,2,\ldots ,N の番号がついており、i\,(1 \leq i \leq N-1) 本目の辺は頂点 u_i と頂点 v_i を結んでいます。

以下の条件を満たす整数 i\,(1 \leq i \leq N) の個数を求めてください。

  • 元の木から頂点 i およびそれに接続する全ての辺を削除して得られるグラフの最大マッチングの大きさが、元の木の最大マッチングの大きさに等しい。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq u_i < v_i \leq N
  • 与えられるグラフは木
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

答えを出力せよ。

入力例 1

3
1 2
2 3

出力例 1

2

元の木の最大マッチングの大きさは 1 です。

頂点 1 およびそれに接続する全ての辺を削除して得られるグラフの最大マッチングの大きさは 1、

頂点 2 およびそれに接続する全ての辺を削除して得られるグラフの最大マッチングの大きさは 0、

頂点 3 およびそれに接続する全ての辺を削除して得られるグラフの最大マッチングの大きさは 1

です。i=1,3 の 2 つが条件を満たすので、2 を出力します。

入力例 2

2
1 2

出力例 2

0

入力例 3

6
2 5
3 5
1 4
4 5
4 6

出力例 3

4

Score : 600 points

Problem Statement

Given is a tree with N vertices. The vertices are numbered 1,2,\ldots,N, and the i-th edge (1 \leq i \leq N-1) connects Vertex u_i and Vertex v_i.

Find the number of integers i (1 \leq i \leq N) that satisfy the following condition.

  • The size of the maximum matching of the graph obtained by deleting Vertex i and all incident edges from the tree is equal to the size of the maximum matching of the original tree.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq u_i < v_i \leq N
  • The given graph is a tree.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3
1 2
2 3

Sample Output 1

2

The size of the maximum matching of the original tree is 1.

The size of the maximum matching of the graph obtained by deleting Vertex 1 and all incident edges from the tree is 1.

The size of the maximum matching of the graph obtained by deleting Vertex 2 and all incident edges from the tree is 0.

The size of the maximum matching of the graph obtained by deleting Vertex 3 and all incident edges from the tree is 1.

Thus, two integers i=1,3 satisfy the condition, so we should print 2.

Sample Input 2

2
1 2

Sample Output 2

0

Sample Input 3

6
2 5
3 5
1 4
4 5
4 6

Sample Output 3

4