#P17711. [2026年江苏省队集训]租房游戏

[2026年江苏省队集训]租房游戏

题目描述

小 H 和小 Q 在城市里租房子,城市可以看作一棵 nn 个点的树,两点之间的距离被定义为连接它们的唯一简单路径所经过的边数。

他们希望选择两个点分别租一个房子,两个房子可以在同一个点上。选择完成后,他们的劳累度被定义为每个点走到任意一个房子的最短距离之和。形式化地说,设选择的点分别为 a,ba,b,则劳累度 f(a,b)=∑u=1nmin⁡(d(u,a),d(u,b))f(a,b)=\sum_{u=1}^n\min(d(u,a),d(u,b)),其中 dd 表示两点之间的距离。

小 Q 希望你在不同的阶段帮他进行一些计算,他会给你一个参数 oo,其中:

  1. o=1o=1:小 H 和小 Q 都没有做出选择,但他们可以进行交流,选择最优的 a,ba,b。请计算 min⁡1≤a,b≤nf(a,b)\min_{1\le a,b\le n}f(a,b)。
  2. o=2o=2:小 H 确定了 a=1a=1,但小 Q 还没有做出决定。请计算 min⁡b=1nf(a,b)\min_{b=1}^n f(a,b)。
  3. o=3o=3:小 H 还没有做出选择,但小 Q 希望对每个小 H 的选择都做好应对方案。请对每个 a∈[1,n]a\in [1,n],计算 min⁡b=1nf(a,b)\min_{b=1}^n f(a,b)。

输入格式

第一行一个整数 TT,表示测试数据组数。

对于每组测试数据:

第一行两个整数 n,on,o,表示点数和参数。

接下来 n−1n-1 行,第 ii 行两个整数 ui,viu_i,v_i,表示树上的一条边。

输出格式

对于每组测试数据:

若 o=1,2o=1,2,输出一行一个整数,表示答案。

若 o=3o=3,输出一行 nn 个整数,第 ii 个整数表示 a=ia=i 时的答案。

样例

样例 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 解释

o=1o=1 时 f(a,b)=1+0+1+0+1+1=4f(a,b)=1+0+1+0+1+1=4。

o=2o=2 时 f(a,b)f(a,b) 在 b=3b=3 时最优,f(a,b)=0+1+0+1+1+2+1=6f(a,b)=0+1+0+1+1+2+1=6。

数据范围与约定

对于全部数据,$1\le T\le 1000,1\le\sum n\le 5\times 10^5,1\le o\le 3$,保证输入给定的是一棵树。

Subtask 分值 ∑n≤\sum n\le 特殊性质
1 6 500500 无
2 7 10510^5 o=3,ui=i,vi=i+1o=3,u_i=i,v_i=i+1
3 11 40004000 无
4 13 10510^5 o=2o=2
5 15 o=1o=1
6 16 3×1043\times 10^4 无
7 20 10510^5
8 12 5×1055\times 10^5