能量树(power)

题目描述

小D梦见了一棵包含$n$个节点的树，这棵树包含着神秘的能量。具体来讲，对于这棵树中的一个联通块，它的能量为它拥有的节点中编号连续的最长的一段。举例来说，如果一个连通块包含了原树中编号为$\{1,3,4,5,7,8\}$的节点，那么编号连续的最长的一段为$\{3,4,5\}$。它所具有的能量值为$3$。

小D想要从这棵树中获得能量，但由于种种原因，小D只能从这棵树中选取一个节点数不大于$k$的连通块并获得它的能量值，小D想要知道他能取得的最大能量值是多少。

一棵树包含$n$个节点的树就是有$n$个点，$n-1$条边的连通图。

输入格式

第一行两个正整数$n$，$k$，分别表示树的大小，选取的子树允许的最大大小。

第二行到第$n$行，每行两个正整数$u$,$v$，表示树上有一条连接节点$u$和节点$v$的边。

输出格式

一行一个整数，表示选取的子树的能量的最大值。

样例

input1

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

output1

3

explanation

选择的联通块节点编号为$\{1,3,4,5,7,8\}$或$\{1,4,6,7,8,10\}$都包含$3$个编号连续的顶点。没有节点数大于$6$的连通块包含大于$3$个编号连续的顶点。

input2

见ex_power2.in。

output2

见ex_power2.ans。

数据范围和约定

对于$10\%$的数据，$n\le20$。

对于$20\%$的数据，$n\le200$。

对于$40\%$的数据，$n\le2000$。

对于另外$15\%$的数据，保证给出的树是一条链。

对于另外$15\%$的数据，保证树随机生成。

对于$100\%$的数据，$n\le100000$,$k\le n$。

时间限制：$1s$ 空间限制：$512MB$

样例下载

样例下载