Home => ProblemSet => 100.2019-06:树的重心
1795: 100.2019-06:树的重心
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 0 Solved: 0[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
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。