1444: 树的重心（centroid）（2019 CCF CSP-S2 day2）
时间限制: 3 Sec 内存限制: 256 MB提交: 1 解决: 1
[提交] [状态] [讨论版] [命题人:]
题目描述
输入
本题输入包含多组测试数据
第一行一个整数 T 表示数据组数。
接下来依次给出每组输入数据，对于每组数据：
第一行一个整数 n 表示树 S 的大小。
接下来 n − 1 行，每行两个以空格分隔的整数 ui, vi，表示树中的一条边 (ui, vi)。
第一行一个整数 T 表示数据组数。
接下来依次给出每组输入数据，对于每组数据：
第一行一个整数 n 表示树 S 的大小。
接下来 n − 1 行，每行两个以空格分隔的整数 ui, vi，表示树中的一条边 (ui, vi)。
输出
共 T 行，每行一个整数，第 i 行的整数表示：第 i 组数据给出的树单独删去每条边 后，分裂出的两个子树的重心编号和之和。
样例输入 Copy
2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
1 4
3 5
3 6
6 7
样例输出 Copy
32
56
提示
【样例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。
【样例2】
见选手目录下的centroid/centroid2.in 与centroid/centroid2.ans。
【样例3】
见选手目录下的centroid/centroid3.in与centroid/centroid3.ans。
该数据满足特殊性质A，具体信息见数据范围中的描述。
【样例4】
见选手目录下的centroid/centroid4.in与centroid/centroid4.ans。
该数据满足特殊性质B，具体信息见数据范围中的描述。
【数据范围】 对于第一组数据：
删去边(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。
【样例2】
见选手目录下的centroid/centroid2.in 与centroid/centroid2.ans。
【样例3】
见选手目录下的centroid/centroid3.in与centroid/centroid3.ans。
该数据满足特殊性质A，具体信息见数据范围中的描述。
【样例4】
见选手目录下的centroid/centroid4.in与centroid/centroid4.ans。
该数据满足特殊性质B，具体信息见数据范围中的描述。
|
测试点编号 |
n= |
特殊性质 |
|
1∼2 |
7 |
无 |
|
3∼5 |
199 |
|
|
6∼8 |
1999 |
|
|
9∼11 |
49991 |
A |
|
12∼15 |
262143 |
B |
|
16 |
99995 |
无 |
|
17∼18 |
199995 |
|
|
19∼20 |
299995 |
A：树的形态是一条链。即∀1≤i<n，存在一条边(pi,pi+1)。
B：树的形态是一个完美二叉树。即∀1≤i≤(n−1)/2，存在两条边(pi,p2i)与(pi,p2i+1)。对于所有测试点：1≤T≤5,1≤ui,vi≤n。保证给出的图是一个树。