← 返回题目列表

AtCoder · abc333_d

G. 擦除叶子

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

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