分数: 600 点
问题陈述
给定的是一棵树 N 顶点。顶点已编号 1,2,\ldots,N,以及 i第边缘 (1 \leq i \leq N-1) 连接顶点 u_i 和顶点 v_i.
查找整数的个数 i (1 \leq i \leq N) 满足以下条件。
- 删除Vertex得到的图的最大匹配大小 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.
删除Vertex得到的图的最大匹配大小 1 并且树中的所有入射边是 1.
删除Vertex得到的图的最大匹配大小 2 并且树中的所有入射边是 0.
删除Vertex得到的图的最大匹配大小 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