← 返回题目列表

AtCoder · abc385_e

H. 雪花树

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

“雪花树”定义为可以通过以下过程生成的树:

  1. 选择正整数 x,y.
  2. 准备一个顶点。
  3. 准备 x 更多顶点,并将它们每个连接到步骤2中准备的顶点。
  4. 对于每个 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