Atcoder ABC 333 - 删除叶子节点

题目描述

给你一棵有N个顶点的树：顶点1,顶点2,……, 顶点N。第i条边(1≤i<N)连接顶点ui​和顶点vi​。

考虑重复下面的操作若干次：

• 选择一个叶顶点v，删除它和所有的附带边。

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

输入描述

第一行一个整数N

接下来N-1行，每个两个数字ui，vi代表一条边连接的两个顶点

数据范围：

• 2≤N≤3×10^5
• 1≤ui​<vi​≤N(1≤i<N)
• 给定图形是一棵树。
• 所有输入值均为整数。

输出描述

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

提示

样例1：

给出的图表如下

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

顶点1无法在四次或更少的操作中删除，因此打印5。