#P17711. [2026年江苏省队集训]租房游戏
[2026年江苏省队集训]租房游戏
题目描述
小 H 和小 Q 在城市里租房子,城市可以看作一棵 个点的树,两点之间的距离被定义为连接它们的唯一简单路径所经过的边数。
他们希望选择两个点分别租一个房子,两个房子可以在同一个点上。选择完成后,他们的劳累度被定义为每个点走到任意一个房子的最短距离之和。形式化地说,设选择的点分别为 ,则劳累度 ,其中 表示两点之间的距离。
小 Q 希望你在不同的阶段帮他进行一些计算,他会给你一个参数 ,其中:
- :小 H 和小 Q 都没有做出选择,但他们可以进行交流,选择最优的 。请计算 。
- :小 H 确定了 ,但小 Q 还没有做出决定。请计算 。
- :小 H 还没有做出选择,但小 Q 希望对每个小 H 的选择都做好应对方案。请对每个 ,计算 。
输入格式
第一行一个整数 ,表示测试数据组数。
对于每组测试数据:
第一行两个整数 ,表示点数和参数。
接下来 行,第 行两个整数 ,表示树上的一条边。
输出格式
对于每组测试数据:
若 ,输出一行一个整数,表示答案。
若 ,输出一行 个整数,第 个整数表示 时的答案。
样例
样例 1 输入
3
6 1
1 2
2 3
2 4
4 5
4 6
7 2
1 2
2 3
3 4
3 5
2 6
1 7
7 3
1 2
2 3
3 4
3 5
2 6
1 7
样例 1 输出
4
6
6 6 6 7 7 8 6
样例 1 解释
时 。
时 在 时最优,。
数据范围与约定
对于全部数据,$1\le T\le 1000,1\le\sum n\le 5\times 10^5,1\le o\le 3$,保证输入给定的是一棵树。
| Subtask | 分值 | 特殊性质 | |
|---|---|---|---|
| 1 | 6 | 无 | |
| 2 | 7 | ||
| 3 | 11 | 无 | |
| 4 | 13 | ||
| 5 | 15 | ||
| 6 | 16 | 无 | |
| 7 | 20 | ||
| 8 | 12 |