删除顶点

题目描述

给定一棵有 $N$ 个顶点的树。顶点编号为 $1,2,\ldots,N$，第 $i$ 条边 $(1 \leq i \leq N-1)$ 连接顶点 $u_i$ 和顶点 $v_i$。

求出满足以下条件的整数 $i$ $(1 \leq i \leq N)$ 的个数。

从树中删除顶点 $i$ 及所有与它关联的边后得到的图的最大匹配的大小，等于原树的最大匹配的大小。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出答案。

样例

3
1 2
2 3

2

原树的最大匹配大小为 $1$。

删除顶点 $1$ 及所有与它关联的边后得到的图的最大匹配大小为 $1$。

删除顶点 $2$ 及所有与它关联的边后得到的图的最大匹配大小为 $0$。

删除顶点 $3$ 及所有与它关联的边后得到的图的最大匹配大小为 $1$。

因此，满足条件的整数有 $i=1,3$ 两个，所以应输出 $2$。

2
1 2

0

6
2 5
3 5
1 4
4 5
4 6

4

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq u_i \lt v_i \leq N$
• 给定图是一棵树。
• 输入中的所有数值均为整数。