Kingdom of Tree

The Kingdom of Tree has $N$ cities numbered from 1 to $N$. The $N$ cities are connected by $N-1$ roads, and any two cities are reachable via a sequence of roads. Obviously, the road system of the Kingdom of Tree is constructed according to a tree structure. That’s how the kingdom’s name comes.

To monitor and protect the roads, the general of the kingdom decides to build radar stations in the cities. We denote the radius of the radar station located in city $i$ as $R_i$. $R_i$ is a non-negative integer, and $R_i=0$ indicates that there is no radar station in city $i$. Given a road connecting city $i$ and city $j$, whose length is denoted as $L_{i,j}$, we say that the road is monitored by radar if $R_i+R_j≥L_{i,j}$.

The cost of building a radar station in city $i$ is proportional to its radius $R_i$. Given a construction plan of the radar stations $P=\{R_1,R_2,...,R_N \}$, we denote the set of monitored roads as S. The cost per length is thus defined as the ratio between the sum of $R_i$ and the sum of the length of monitored roads: $\sum_{i=1}^{N} R_{i}/\sum_{(i,j)∈S}L_{i,j}$.

Due to limited budget, the general wants to make the most of the money. He wants a construction plan that minimizes the cost per length. Note that he don’t have to monitor all the roads. As the most brilliant programmer of the Kingdom of Tree, can you help him to find such a construction plan?

The first line of input contains a number $T$ indicating the number of test cases ($T≤200$).

Each test case starts with a line containing an integer $N$ indicating the number of cities ($2≤N≤30$). Each of the next $N-1$ lines contains three integers $i, j$, and $k$, indicating that there is a road between city $i$ and city $j$, and its length is $k$. ($1≤i≠j≤N,1≤k≤10^9$ )

It is guaranteed that any two cities are reachable via a sequence of roads.

For each test case, output a single line consisting of “Case #X: Y”. $X$ is the test case number starting from 1. $Y$ is the minimum cost per length. You answer is considered correct if its absolute error is less than $10^{-6}$.

4
7
1 2 1
2 3 2
3 4 99
4 5 3
5 6 1
6 7 4
4
1 2 3
2 3 2
2 4 1
5
1 2 2
2 3 1
3 4 2
3 5 5
2
1 2 3

Case #1: 0.66666667
Case #2: 0.50000000
Case #3: 0.62500000
Case #4: 1.00000000

2015ACM/ICPC亚洲区合肥站-重现赛（感谢中科大）