AT_abc333_d [ABC333D] Erase Leaves

题目描述

给定一棵包含 $N$ 个顶点的树，顶点编号为 $1, 2, \ldots, N$。第 $i$ 条边 $(1 \leq i < N)$ 连接顶点 $u_i$ 和 $v_i$。

你可以重复进行如下操作任意次：

• 选择一个叶子顶点 $v$，将顶点 $v$ 及其所有连接的边删除。

请你求出，最少需要进行多少次操作才能删除顶点 $1$。

什么是树？树是指无向图中连通且无环的图。详细内容请参考：Wikipedia「木 (数学)」。

什么是叶子？树中的叶子是指度数不超过 $1$ 的顶点。

输入格式

输入通过标准输入按以下格式给出。

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

输出格式

请输出答案，输出一行。

输入输出样例 #1

输入 #1

9
1 2
2 3
2 4
2 5
1 6
6 7
7 8
7 9

输出 #1

5

输入输出样例 #2

输入 #2

6
1 2
2 3
2 4
3 5
3 6

输出 #2

1

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq u_i < v_i \leq N\ (1 \leq i < N)$
• 给定的图为树
• 输入均为整数

样例解释 1

给定的图如下所示。

例如，按 $9, 8, 7, 6, 1$ 的顺序选择顶点进行操作，可以在 $5$ 次操作内删除顶点 $1$。

无法在 $4$ 次或更少的操作内删除顶点 $1$，因此应输出 $5$。

样例解释 2

在给定的图中，顶点 $1$ 是叶子。因此，在第 $1$ 次操作时即可选择顶点 $1$ 并将其删除。

由 ChatGPT 4.1 翻译