#483. [CSP-S 2026] 研发基地
[CSP-S 2026] 研发基地
研发基地(hub)
CSP-S 2026 第二轮 · T4(赛题题意整理,测试数据为自制)
题目描述
有 座城市及 条无向道路,城市和道路构成一棵树。要在恰好 座不同城市建造基地。仅保留选中的城市和它们之间原本存在的道路时,选中城市形成的连通块数量必须不超过两个。
对一个方案 ,每座城市 的通勤距离是它到最近基地的树上距离:。方案的通勤半径是所有城市中通勤距离的最大值。
求满足限制的方案的最小通勤半径。
输入格式
第一行两个非负整数 ,表示测试点编号和数据组数, 不影响答案。
每组数据第一行两个整数 ;随后 行,每行两个整数 ,表示树的一条无向边。
输出格式
对每组数据输出一行非负整数,表示最优通勤半径。
输入输出样例 #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
数据范围与说明
,单组 、,单个文件 ,;给出的 条边保证构成一棵树。
注意连通块限制是“不超过两个”,允许所有选中点只形成一个连通块;必须恰好选择 个点。
注意: Hydro 使用标准输入输出;测试数据自行生成,并非 CCF 官方测试数据。