#483. [CSP-S 2026] 研发基地

[CSP-S 2026] 研发基地

研发基地(hub)

CSP-S 2026 第二轮 · T4(赛题题意整理,测试数据为自制)

题目描述

有 nn 座城市及 n−1n-1 条无向道路,城市和道路构成一棵树。要在恰好 kk 座不同城市建造基地。仅保留选中的城市和它们之间原本存在的道路时,选中城市形成的连通块数量必须不超过两个。

对一个方案 SS,每座城市 ii 的通勤距离是它到最近基地的树上距离:d(i)=min⁡j∈Sdist⁡(i,j)d(i)=\min_{j\in S}\operatorname{dist}(i,j)。方案的通勤半径是所有城市中通勤距离的最大值。

求满足限制的方案的最小通勤半径。

输入格式

第一行两个非负整数 c,tc,t,表示测试点编号和数据组数,cc 不影响答案。

每组数据第一行两个整数 n,kn,k;随后 n−1n-1 行,每行两个整数 u,vu,v,表示树的一条无向边。

输出格式

对每组数据输出一行非负整数,表示最优通勤半径。

输入输出样例 #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
2

数据范围与说明

1≤t≤51\le t\le5,单组 2≤n≤1062\le n\le10^6、2≤k≤n2\le k\le n,单个文件 ∑n≤2×106\sum n\le2\times10^6,0≤c≤200\le c\le20;给出的 n−1n-1 条边保证构成一棵树。

注意连通块限制是“不超过两个”,允许所有选中点只形成一个连通块;必须恰好选择 kk 个点。

注意: Hydro 使用标准输入输出;测试数据自行生成,并非 CCF 官方测试数据。