#P11533. [2024省队模拟]排列

[2024省队模拟]排列

题目描述

有一颗树,你需要求出一个排列 pp ,使得 ∑(u,v)是一条树上的边∣pu−pv∣\sum_{(u,v)是一条树上的边}|p_{u}-p_{v}| 最小,请输出最小值。

输入格式

第一行输入一个正整数 TT ,表示有 TT 组数据。 接下来对于每组数据输入两个正整数 nn ,接下来 n−1n-1 行,每行输入一条边 (x,y)(x,y) ,表示树上的一条边。

输出格式

输出 TT 行表示答案。

样例输入1

1
5
1 2
1 3
2 4
2 5

样例输出1

5

样例输入2

1
10
1 2
2 3
3 4
3 5
1 6
2 7
2 8
7 9
3 10

样例输出2

14

数据规模和约定

测试点编号     ∑n\;\;\sum{n} 特殊性质
1−21-2 ≤10≤10 无
3−43-4 ≤106≤10^6 A
5−85-8 B
9−109-10 ≤102≤10^2 无
11−1411-14 ≤103≤10^3
15−1615-16 ≤105≤10^5
17−2017-20 ≤106≤10^6

特殊性质AA:仅有一个节点的度数>2>2。

特殊性质BB:每个点的儿子个数≤10≤10。

对于所有测试点均满足 T,∑n≤106T , \sum n≤10^6。