G - 删除节点

得分 : $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}$

输出

输出答案。

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$。

从树中删除顶点 $1$ 以及连接到该顶点的所有边所得到的图的最大匹配大小为 $2$。

从树中删除顶点 $2$ 以及连接到该顶点的所有边所得到的图的最大匹配大小为 $2$。

从树中删除顶点 $3$ 以及连接到该顶点的所有边所得到的图的最大匹配大小为 $2$。

从树中删除顶点 $4$ 以及连接到该顶点的所有边所得到的图的最大匹配大小为 $2$。

从树中删除顶点 $5$ 以及连接到该顶点的所有边所得到的图的最大匹配大小为 $1$。

从树中删除顶点 $6$ 以及连接到该顶点的所有边所得到的图的最大匹配大小为 $1$。

满足条件的四个整数 $i=1,2,3,4$，所以我们应该输出 $4$。