← 返回题目列表

AtCoder · abc223_g

G. 顶点删除

中文机器翻译题面 查看原题

分数: 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