Average distance

Interview

Time limit1sMemory limit1024 MB

Summary

Given a weighted tree, compute the average distance over all unordered pairs of vertices, within 1e-6 relative or absolute error.

Level: Medium6 of 10
Topics: Tree, DFS, Dynamic programming, Math
Solved: No attempts yet

Problem

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.

Figure 1: The first sample case

Input

The first line contains 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 test case:

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.

Examples1

Example 1
Input
```
1
5
0 1 6
0 2 3
0 3 7
3 4 2
```
Expected output
```
8.6
```