P17834 [CSP-S 2026] 研发基地 / hub（民间数据）

考虑评测机性能差异，时限临时增加 1 秒。

小 W 曾是一名科研爱好者。在 C 国工作时，他担任测试员，日复一日地测试各种新型传送门，在城市之间来回穿梭。久而久之，他厌倦了这样的生活，于是辞去工作，来到没有任何传送门的 D 国，希望在这里重新找回对研发的热爱。 在开始研发之前，小 W 需要建造研发基地。D 国共有 $n$ 座城市，编号为 $1$ 到 $n$。这 $n$ 座城市由 $n-1$ 条道路连接，其中第 $i\ (1\le i\le n-1)$ 条道路连接第 $u_i$ 座和第 $v_i$ 座城市。若将每座城市视作一个点，将每条道路视作连接两个点的边，则这 $n$ 座城市和 $n-1$ 条道路构成一棵树 $T$。 小 W 的经费有限，他计划选择**恰好** $k$ 座城市，在每座选中的城市里各建造一个研发基地。为了便于这些基地之间的协作，小 W 希望选中的城市在 $T$ 中对应的点形成**不超过两个连通块**。形式化地，定义建造方案 $S\subseteq\{1,2,\ldots,n\}$ 是**合理的**，当且仅当 $|S|=k$，且 $S$ 在 $T$ 中形成的连通块数量不超过 $2$。 对于合理的建造方案 $S$，定义第 $i\ (1\le i\le n)$ 座城市的**通勤距离**为 $d(i)=\min_{j\in S}\operatorname{dist}(i,j)$，其中 $\operatorname{dist}(i,j)$ 表示从第 $i$ 座城市到第 $j$ 座城市所需经过的道路的最少条数。特别地，若 $i\in S$，则 $d(i)=0$。定义该建造方案的**通勤半径**为所有城市通勤距离的最大值，即 $\max_{i=1}^{n}d(i)$。 你需要帮助小 W 求出，所有合理的建造方案的通勤半径的最小值。

从文件 `hub.in` 中读入数据。 **本题包含多组测试数据。** 输入的第一行包含两个非负整数 $c,t$，分别表示测试点编号与测试数据组数。特别地，若 $c=0$，则该测试点为样例。 接下来依次输入 $t$ 组测试数据。对于每组测试数据： - 第一行包含两个正整数 $n,k$，分别表示城市数量和小 W 计划建造的研发基地数量。 - 第 $i+1\ (1\le i\le n-1)$ 行包含两个正整数 $u_i,v_i$，分别表示第 $i$ 条道路连接的两座城市的编号。

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

### 样例 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$。 ### 样例 2 见题目目录下的 `hub/2.in` 与 `hub/2.ans`。 该样例满足测试点 $2,3$ 的约束条件。 ### 样例 3 见题目目录下的 `hub/3.in` 与 `hub/3.ans`。 该样例满足测试点 $8$ 的约束条件。 ### 样例 4 见题目目录下的 `hub/4.in` 与 `hub/4.ans`。 该样例满足测试点 $11,12$ 的约束条件。 ### 样例 5 见题目目录下的 `hub/5.in` 与 `hub/5.ans`。 该样例满足测试点 $13,14$ 的约束条件。 ### 数据范围 设 $N$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试数据，均有： - $0\le c\le 20$，$1\le t\le 5$； - $2\le n\le 10^6$，$N\le 2\times 10^6$，$2\le k\le n$； - 对于所有 $i\ (1\le i\le n-1)$，均有 $1\le u_i,v_i\le n$，且所有 $(u_i,v_i)$ 构成一棵树。 ::cute-table{tuack} | 测试点编号 | $n\le$ | $N\le$ | $k\le$ | 特殊性质 | | :---: | :---: | :---: | :---: | :---: | | $1$ | $5$ | $15$ | $5$ | 无 | | $2,3$ | $10$ | $30$ | $10$ | ^ | | $4\sim 6$ | $100$ | $300$ | $100$ | ^ | | $7$ | $1000$ | $3000$ | $2$ | ^ | | $8$ | ^ | ^ | $1000$ | ^ | | $9,10$ | $4000$ | $10^4$ | $4000$ | ^ | | $11,12$ | $10^5$ | $3\times 10^5$ | $2$ | ^ | | $13,14$ | ^ | ^ | $10^5$ | A | | $15$ | $5\times 10^5$ | $10^6$ | $10$ | 无 | | $16,17$ | ^ | ^ | $5\times 10^5$ | ^ | | $18\sim 20$ | $10^6$ | $2\times 10^6$ | $10^6$ | ^ | 特殊性质 A：存在正整数 $m$ 满足 $n=2m+1$，且对于所有 $i\ (1\le i\le m)$，均有 $u_i=i$ 且 $v_i=i+1$；对于所有 $i\ (m+1\le i\le n-1)$，均有 $u_i=i-m$ 且 $v_i=i+1$。