分数: 450 点
问题陈述
“雪花树”定义为可以通过以下过程生成的树:
- 选择正整数 x,y.
- 准备一个顶点。
- 准备 x 更多顶点,并将它们每个连接到步骤2中准备的顶点。
- 对于每个 x 步骤 3 中准备的顶点,附加 y 留给它。
下图显示了一棵雪花树 x=4,y=2。步骤 2、3、4 中准备的顶点分别以红色、蓝色和绿色显示。

你得到一棵树 T 与 N 顶点。顶点已编号 1 to N,以及 i第边缘 (i=1,2,\dots,N-1) 连接顶点 u_i 和 v_i.
考虑删除 的零个或多个顶点 T 以及与它们相邻的边,以便剩余的图成为单个雪花树。找到必须删除的最少顶点数。在这个问题的约束下,总是可以改造的 T 变成雪花树。
约束
- 3 \leq N \leq 3 \times 10^5
- 1 \leq u_i < v_i \leq N
- 给定的图是一棵树。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
输出
打印答案。
示例输入 1
8 1 3 2 3 3 4 4 5 5 6 5 7 4 8
示例输出 1
1
通过删除顶点 8,给定的树可以转换为雪花树 x=2,y=2.
示例输入 2
3 1 2 2 3
示例输出 2
0
给定的树已经是一棵雪花树 x=1,y=1.
示例输入 3
10 1 3 1 2 5 7 6 10 2 8 1 6 8 9 2 7 1 4
示例输出 3
3