3718: 方差(第三轮04)
题目描述
你有一棵 n 个点， n − 1 条边的无根树，但是树没有根是活不了的，所以你需 要给树找一个根。有了根之后， 每个点到根的距离都可以算出来（每条边的长度 为 1，根到根的距离为 0），那么你就可以得到一个长度为 n 的序列 a。为了尽 可能地使得每个点均匀地吸收养分，你想要让这个序列的方差尽可能的小！
为了确保答案是一个整数，请你输出方差乘以 n2
的结果。具体来说，假设这个序列的平均值为 x，你需要输出的是：
输入
第一行输入一个正整数 t(1 ≤ t ≤ 5)，表示共有 t 组数据。
每组数据的第一行输入一个正整数 n，接下来包含 n − 1 行。
每行给出两个正整数 a, b，表示 a, b 之间有一条边。
输出
输出 t 行，每行一个整数表示结果。
样例输入 复制
1
4
1 2
1 3
1 4样例输出 复制
3提示
【样例 1 输入】
1
4
1 2
1 3
1 4
【样例 1 输出】
3
【样例 1 说明】
选择 1 作为根，则 1 、2 、3 、4 这四个点到根的距离分别为 [0,1,1,1]，这个数 组的平均值为 0.75， 计算 4 * ((0 − 0.75)2 + (1 − 0.75)2 + (1 − 0.75)2 + (1 − 0.75)2) = 3
【样例 2 输入】
1
4
1 2
1 3
3 4
【样例 2 输出】
8
【样例 2 说明】
选择 1 作为根，则四个点到根的距离分别为 [0,1,1,2]，平均值为 1，计算 4 * ((0 − 1)2 + (1 − 1)2 + (1 − 1)2 + (2 − 1)2) = 8
【样例 3 输入】
2
4
1 2
1 3
3 4
10
6 4
2 3
1 5
7 1
8 4
1 2
9 3
10 2
3 4
【样例 3 输出】
8
81
【数据范围】
本题共 10 个测试点：
对于 1 测试点，有 1 ≤ n ≤ 100
对于 2 − 3 测试点，有 1 ≤ n ≤ 1000 对于 4 − 5 测试点，这棵树是一条链
对于所有测试点，有 1 ≤ n ≤ 40000,1 ≤ t ≤ 5