4235: Erase Leaves

# Erase Leaves ### 内存 1024MB ### 时间 2S ## 题目描述 给定一棵有$N$个顶点的树：顶点1、顶点2、...、顶点$N$。第$i$条边$(1 ≤ i < N)$连接顶点$u_i$和$v_i$。 考虑重复执行以下操作若干次： - 选择一个叶子顶点$v$并删除它以及所有与之相连的边。 找出删除顶点1所需的最少操作次数。 - 什么是树？树是一种无向图，它是连通的且没有环。 - 什么是叶子？树中的叶子是指度数最多为1的顶点。 ## 输入格式 输入从标准输入中以下列格式给出： $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 ``` ### 输入样例2 ``` 6 1 2 2 3 2 4 3 5 3 6 ``` ### 输出样例2 ``` 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 ``` ## 数据范围与提示 【样例1说明】 给定的图如下所示：  例如，你可以按9、8、7、6、1的顺序选择顶点，通过五次操作删除顶点1。  顶点1无法通过四次或更少的操作删除，所以输出5。 【样例2说明】 在给定的图中，顶点1是一个叶子。因此，你可以在第一次操作中选择并删除顶点1。 【数据范围】 - $2 ≤ N ≤ 3 × 10^5$ - $1 ≤ u_i < v_i ≤ N (1 ≤ i < N)$ - 给定的图是一棵树 - 所有输入值都是整数。 ## 题目来源 ABC333D