分数: 600 点
问题陈述
给定一棵无向树,令顶点之间的距离 u 和 v 是 简单路径上的边数 u to v。 树的直径是任意两个顶点之间的距离中的最大值。 我们将调用一棵树 好 当且仅当其直径最大为 K.
给你一棵无向树 N 顶点编号 1 通过 N。 对于每个 i (1≦i≦N-1),有一条边连接顶点 A_i 和 B_i.
您想要从树中删除零个或多个顶点,以便生成的树是好的。 当删除一个顶点时,所有关联边也将被删除。 所得到的图必须是连接的。
找到生成一棵好树所需删除的最少顶点数。
约束
- 2≦N≦2000
- 1≦K≦N-1
- 1≦A_i≦N, 1≦B_i≦N
- 该图定义为 A_i 和 B_i 是一棵树。
输入
输入由标准输入按以下格式给出:
N K
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}
输出
打印生成一棵好树所需删除的最小顶点数。
示例输入 1
6 2 1 2 3 2 4 2 1 6 5 6
示例输出 1
2
树如下所示。删除顶点 5 和 6 将生成一棵直径为的好树 2.
示例输入 2
6 5 1 2 3 2 4 2 1 6 5 6
示例输出 2
0
由于给定的树已经很好,因此您不需要删除任何顶点。