1586: 【CSP2019-S-D2T3】树的重心
[Creator : ]
Submit
Description
Input
本题输入包含多组测试数据。
第一行一个整数 T 表示数据组数。
接下来依次给出每组输入数据，对于每组数据：
第一行一个整数 n 表示树 S 的大小。
接下来 n−1 行，每行两个以空格分隔的整数 ui,vi，表示树中的一条边 (ui,vi)。
第一行一个整数 T 表示数据组数。
接下来依次给出每组输入数据，对于每组数据：
第一行一个整数 n 表示树 S 的大小。
接下来 n−1 行，每行两个以空格分隔的整数 ui,vi，表示树中的一条边 (ui,vi)。
Output
共 T 行，每行一个整数，第 i 行的整数表示：第 i 组数据给出的树单独删去每条边后，分裂出的两个子树的重心编号和之和。
Sample Input Copy
2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
1 4
3 5
3 6
6 7
Sample Output Copy
32
56
HINT
【样例 1 解释】
对于第一组数据：
删去边 (1, 2)，1 号点所在子树重心编号为 {1}，2 号点所在子树重心编号为 {2, 3}。
删去边 (2, 3)，2 号点所在子树重心编号为 {2}，3 号点所在子树重心编号为 {3, 5}。
删去边 (2, 4)，2 号点所在子树重心编号为 {2, 3}，4 号点所在子树重心编号为 {4}。
删去边 (3, 5)，3 号点所在子树重心编号为 {2}，5 号点所在子树重心编号为 {5}。
因此答案为 1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32。
【数据规模与约定】
对于第一组数据：
删去边 (1, 2)，1 号点所在子树重心编号为 {1}，2 号点所在子树重心编号为 {2, 3}。
删去边 (2, 3)，2 号点所在子树重心编号为 {2}，3 号点所在子树重心编号为 {3, 5}。
删去边 (2, 4)，2 号点所在子树重心编号为 {2, 3}，4 号点所在子树重心编号为 {4}。
删去边 (3, 5)，3 号点所在子树重心编号为 {2}，5 号点所在子树重心编号为 {5}。
因此答案为 1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32。
【数据规模与约定】