4518. 研发基地

【题目描述】

小W 曾是一名科研爱好者。在C 国工作时，他担任测试员，日复一日地测试各种新型传送门，在城市之间来回穿梭。久而久之，他厌倦了这样的生活，于是辞去工作，来到没有任何传送门的D 国，希望在这里重新找回对研发的热爱。

在开始研发之前，小W 需要建造研发基地。D 国共有n 座城市，编号为1 到n。这n 座城市由n − 1 条道路连接，其中第i (1 ≤ i ≤ n − 1) 条道路连接第ui  座和第vi座城市。若将每座城市视作一个点，将每条道路视作连接两个点的边，则这n 座城市和 n − 1 条道路构成一棵树T。

小W 的经费有限，他计划选择恰好k 座城市，在每座选中的城市里各建造一个研发基地。为了便于这些基地之间的协作，小W 希望选中的城市在T  中对应的点形成不超过两个连通块。形式化地，定义建造方案S ⊆ {1 ,2 ,...,n} 是合理的，当且仅当|S| = k，且S 在T 中形成的连通块数量不超过2。

对于合理的建造方案S，定义第i  (1  ≤  i  ≤  n)  座城市的通勤距离为d (i)  = minj∈S dist (i,j)，其中dist (i,j)  表示从第i 座城市到第j  座城市所需经过的道路的最少条数。特别地，若i ∈ S，则d (i) = 0。定义该建造方案的通勤半径为所有城市通勤距离的最大值，即maxd (i)。你需要帮助小W 求出，所有合理的建造方案的通勤半径的最小值。

【输入格式】

从文件hub.in 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数c,t，分别表示测试点编号与测试数据组数。特别地，若c = 0，则该测试点为样例。

接下来依次输入t 组测试数据。对于每组测试数据：

• 第一行包含两个正整数n,k，分别表示城市数量和小W 计划建造的研发基地数量。

• 第i + 1 (1 ≤ i ≤ n − 1) 行包含两个正整数ui ,vi，分别表示第i 条道路连接的两座城市的编号。

【输出格式】

输出到文件hub.out 中。对于每组测试数据，输出一行一个非负整数，表示所有合理的建造方案的通勤半径的最小值。

【样例1输入】

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

【样例1输出】

1
2

【样例1说明】

该样例共包含两组测试数据。

对于第一组测试数据，共有10 种合理的建造方案。按通勤半径分类如下：

• 通勤半径为1 的方案：S = {1 ,4}，S = {2 ,4}，S = {2 ,5}；

• 通勤半径为2 的方案：S = {1 ,3}，S = {1 ,5}，S = {2 ,3}，S = {3 ,4}，S = {3 ,5}；

• 通勤半径为3 的方案：S = {1 ,2}，S = {4 ,5}。

因此，所有合理的建造方案的通勤半径的最小值为1。对于第二组测试数据，一种合理的建造方案为S = {2 ,7 ,9}，其中第2 座城市单独构成一个连通块，第7 座和第9 座城市构成一个连通块。该建造方案的通勤半径为2。

【数据规模与约定】

【来源】

在此键入。