102236: [AtCoder]ABC223 G - Vertex Deletion

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

问题描述

给定一个具有$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
1 2

样例输出2

0

样例输入3

6
2 5
3 5
1 4
4 5
4 6

样例输出3

4