Rebuilding Roads for Maximum Average Value

X Country has been devastated by an earthquake, leaving its transportation network nearly paralyzed. In order to rebuild, the reconstruction team proposes to select a subset of the originally planned N-1 roads (which connect N cities in a spanning tree) to form a new plan. The team has computed a value v(e) for each road e that represents the potential benefit of rebuilding that road. Due to budget constraints, the government stipulates that the first phase must build exactly k roads satisfying L \le k \le U, and these k roads must form a simple path. In other words, if the rebuilt roads form a sequence e₁=(p₁,q₁), e₂=(p₂,q₂), …, e_k=(p_k,q_k), then for all 1 \le i < k it holds that q_i = p_i+1.

The objective is to choose a simple path S (with number of roads k such that L \le k \le U) from the original spanning tree so that the average value

is maximized. It is guaranteed that the given bounds L and U allow at least one valid solution. Help the reconstruction team find the optimal plan by computing the maximum possible average value of the selected road path.

inputFormat

The first line contains three integers N, L, and U where N is the number of cities, and L and U are the lower and upper bounds for the number of roads to be rebuilt. Each of the following N-1 lines contains three integers u, v, and w indicating that there is a road connecting cities u and v with value w.

outputFormat

Output a single line containing the maximum average value achievable by a simple path (with a number of roads between L and U). The answer should be printed with exactly 6 decimal places.

sample

5 1 3
1 2 4
2 3 3
2 4 2
4 5 6

6.000000