Erase Leaves

题目描述

你被给定了一个有 $N$ 个顶点的树：顶点 $1$，顶点 $2$，$\ldots$，顶点 $N$。 第 $i$ 条边 $(1\leq i\lt N)$ 连接顶点 $u _ i$ 和 顶点 $v _ i$。 考虑重复执行以下操作若干次：

选择一个叶子顶点 $v$ 并删除它以及与之相连的所有边。

求删除顶点 $1$ 所需的最少操作次数。

输入格式

输入从标准输入按以下格式给出： $N$ $u _ 1$ $v _ 1$ $u _ 2$ $v _ 2$ $\vdots$ $u _ {N-1}$ $v _ {N-1}$

输出格式

在一行中打印答案。

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

5

6
1 2
2 3
2 4
3 5
3 6

1

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

12

提示

$2\leq N\leq3\times10^5$ $1\leq u _ i\lt v _ i\leq N\ (1\leq i\lt N)$ 给定的图是一个树。 所有输入值都是整数。给定的图如下所示： 例如，你可以按顺序选择顶点 $9,8,7,6,1$ 来在五次操作中删除顶点 $1$。 顶点 $1$ 无法在四次或更少操作中被删除，所以输出 $5$.
在给定的图中，顶点 $1$ 是一个叶子。 因此，你可以在第一次操作中选择并删除顶点 $1$。

标签: AtCoder|abc333D

来源

AtCoder|abc333D