树的重心

提交数: 166, 通过率: 19.28%, 平均分: 30.39

题目描述:

157758523010813990.png

输入格式:

本题包含多组测试数据

第一行一个整数 T 表示数据组数。

接下来依次给出每组输入数据,对于每组数据:

第一行一个整数 n 表示树 S 的大小。

接下来 n−1 行,每行两个以空格分隔的整数 ui​,vi​,表示树中的一条边 (ui​,vi​)。

输出格式:

共 T 行,每行一个整数,第 i 行的整数表示:第 i 组数据给出的树单独删去每条边后,分裂出的两个子树的重心编号和之和。

样例输入:

2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
1 4
3 5
3 6
6 7

样例输出:

32
56

提示:

1577585326582392346.png

时间限制: 4000ms
空间限制: 256MB

来源: CSP2019提高T6