分数: 400 点
问题陈述
你得到了一棵树 N 顶点:顶点 1, 顶点 2, \ldots,顶点 N。 的 i第边缘 (1\leq i\lt N) 连接顶点 u _ i 和顶点 v _ i.
考虑重复以下操作一定次数:
- 选择一个叶子顶点 v 并将其与所有关联边一起删除。
求删除顶点所需的最少操作数 1.
什么是树?
树是一种连通且没有环的无向图。 有关更多详细信息,请参阅: 维基百科“树(图论)”.什么是叶子?
树中的叶子是度数最多为 的顶点 1.约束
- 2\leq N\leq3\times10^5
- 1\leq u _ i\lt v _ i\leq N\ (1\leq i\lt N)
- 给定的图是一棵树。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ {N-1} v _ {N-1}
输出
在一行中打印答案。
示例输入 1
9 1 2 2 3 2 4 2 5 1 6 6 7 7 8 7 9
示例输出 1
5
给定的图表如下所示:

例如,您可以选择顶点 9,8,7,6,1 按此顺序删除顶点 1 五次操作。

顶点 1 无法通过四次或更少的操作来删除,因此打印 5.
示例输入 2
6 1 2 2 3 2 4 3 5 3 6
示例输出 2
1
在给定的图中,顶点 1 是一片叶子。 因此,您可以选择并删除顶点 1 在第一次操作中。
示例输入 3
24 3 6 7 17 7 20 7 11 14 18 17 21 6 19 5 22 9 24 11 14 6 23 8 17 9 12 4 17 2 15 1 17 3 9 10 16 7 13 2 16 1 16 5 7 1 3
示例输出 3
12