229 . Average distance
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 Format
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<=10000): 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 <= 1000). There is an edge between the nodes with numbers a and b of length d. The resulting graph will be a tree.
Output Format
For each testcase:
• One line with the average distance between two vertices with 3 decimal digits.
Sample Input 1
1 5 0 1 6 0 2 3 0 3 7 3 4 2
Sample Output 1
8.600
Hints
Problem Source
Migrated from old NTUJ.
Subtasks
| No. | Testdata Range | Score |
|---|