Vertex Deletion

题目描述

给定一棵有 $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

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 < v_i \leq N 所给图是树。 输入中的所有值都是整数。原始树的最大匹配的大小是 $1$。 从树中删除顶点 $1$ 及所有与之相连的边后得到的图的最大匹配的大小是 $1$。 从树中删除顶点 $2$ 及所有与之相连的边后得到的图的最大匹配的大小是 $0$。 从树中删除顶点 $3$ 及所有与之相连的边后得到的图的最大匹配的大小是 $1$。 因此，有两个整数 $i=1,3$ 满足该条件，所以我们应当输出 $2$.

标签: AtCoder|abc223G

来源

AtCoder|abc223G