编程介的小学生 2019-09-22 21:55 采纳率: 20.5%
浏览 149

Average distance 平均距离

Problem Description
Given a tree, calculate the average distance between two vertices in the tree. For example, the average distance between two vertices in the following tree is (d01 + d02 + d03 + d04 + d12 +d13 +d14 +d23 +d24 +d34)/10 = (6+3+7+9+9+13+15+10+12+2)/10 = 8.6.

Input
On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with an integer n (2 <= n <= 10 000): the number of nodes in the tree. The nodes are numbered from 0 to n - 1.

n - 1 lines, each with three integers a (0 <= a < n), b (0 <= b < n) and d (1 <= d <= 1 000). There is an edge between the nodes with numbers a and b of length d. The resulting graph will be a tree.

Output
For each testcase:

One line with the average distance between two vertices. This value should have either an absolute or a relative error of at most 10-6

Sample Input
1
5
0 1 6
0 2 3
0 3 7
3 4 2

Sample Output
8.6

  • 写回答

0条回答

    报告相同问题?

    悬赏问题

    • ¥100 关于使用MATLAB中copularnd函数的问题
    • ¥20 在虚拟机的pycharm上
    • ¥15 jupyterthemes 设置完毕后没有效果
    • ¥15 matlab图像高斯低通滤波
    • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
    • ¥15 钢筋实图交点识别,机器视觉代码
    • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
    • ¥50 400g qsfp 光模块iphy方案
    • ¥15 两块ADC0804用proteus仿真时,出现异常
    • ¥15 关于风控系统,如何去选择