← 返回题目列表

Codeforces · 372/D

D. 选择子树很有趣

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

有一棵由n个顶点组成的树。顶点编号为 1 到 n。

让我们将区间 [l, r] 的长度定义为值 r - l + 1。这棵树的子树的分数是区间 [l, r] 的最大长度,其中编号为 l, l + 1, ..., r 的顶点属于该子树。

考虑树中大小至多为 k 的所有子树,返回子树的最大分数。请注意,在这个问题中,树没有根,因此子树是树的任意连通子图。

输入

第一行有两个整数,n 和 k (1 ≤ k ≤ n ≤ 105)。接下来的 n - 1 行中的每一行都包含整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi)。这意味着 ai 和 bi 通过树边连接。

保证输入代表一棵树。

输出

输出应包含一个整数 - 最大可能分数。

示例

输入 #1

10 6
4 10
10 6
2 9
9 6
8 5
7 1
4 7
7 3
1 8

输出 #1

3

输入 #2

16 7
13 11
12 11
2 14
8 6
9 15
16 11
5 14
6 15
4 3
11 15
15 14
10 1
3 14
14 7
1 7

输出 #2

6

注意

对于第一种情况,存在一些子树,其大小最多为6,包括3个连续的顶点数。例如,由{1,3,4,5,7,8}或{1,4,6,7,8,10}组成的子树包括3个连续的顶点。但不存在大小最大为 6 且包含 4 个或更多连续顶点的子树。