Average distance

Time Limit: 2 Seconds
Memory Limit: 65536 KB
Special Judge

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 (d_{01} + d_{02} + d_{03} + d_{04} + d_{12} +d_{13} +d_{14} +d_{23} +d_{24} +d_{34})/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^{-3}

**Sample Input**

1

5

0 1 6

0 2 3

0 3 7

3 4 2

**Sample Output**

8.6

Source:

**The 2007 Benelux Algorithm Programming Contest**
Submit
Status