← 返回题目列表

AtCoder · agc001_c

C. 缩短直径

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

分数: 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.

ctree.png

示例输入 2

6 5
1 2
3 2
4 2
1 6
5 6

示例输出 2

0

由于给定的树已经很好,因此您不需要删除任何顶点。