Description

Country X was heavily hit by an earthquake, which almost paralyzed nationwide transportation, and the reconstruction plan is urgent. Country X consists of $N$ cities. The reconstruction team proposed that building only $N - 1$ roads would make any two cities mutually reachable. Thus, they quickly proposed a plan containing $N - 1$ roads that ensures pairwise reachability between cities, and they also evaluated the value $v(e)$ that each road $e$ would bring after construction.

Due to the complexity and difficulty of the reconstruction plan, and with limited funds, the government requires that the number of roads to be built in the first phase be $k$, with $L \leq k \leq U$, i.e., no fewer than $L$ roads and no more than $U$ roads. Meanwhile, to maximize utilization, the selected roads must form exactly one simple path, i.e., the $k$ roads can be arranged as a sequence $e_1 = (p_1, q_1), e_2 = (p_2, q_2), \cdots, e_k = (p_k, q_k)$ such that for $1 \leq i < k$ we have $(q_i = p_{i+1})$.

The reconstruction team plans to modify their original plan to meet the requirement, that is, find a path $S$ among the original $N - 1$ roads as the new plan, so that the average value of the new plan

is maximized. Here $v(e)$ denotes the value of road $e$, and $|S|$ is the number of roads in the new plan. Please help the reconstruction team find an optimal plan. Note: In this problem, $L$ and $U$ are set to guarantee a solution.

Input Format

The first line contains a positive integer $N$, the number of cities in Country X.

The second line contains two positive integers $L, U$, the lower and upper bounds on the number of roads to be built in the first-phase plan.

Each of the next $N - 1$ lines describes the original plan of the reconstruction team, with three positive integers $a_i, b_i, v_i$, indicating a road $(a_i, b_i)$ whose value is $v_i$. Cities are numbered $1 \cdots N$.

Output Format

Output a single line containing a real number AvgValue, the maximum average value.

Keep three digits after the decimal point.

4 
2 3 
1 2 1 
1 3 2 
1 4 3

2.500

Hint

In the new plan, selecting the path $(3, 1), (1, 4)$ yields an average value of $2.5$, which is the maximum average value.

For 20% of the testdata, $N \leq 5000$.

For another 30% of the testdata, $N \leq 100000$, and the original plan is exactly a path (chain).

For 100% of the testdata, $N \leq 100000$, $1 \leq L \leq U \leq N - 1$, and $v_i \leq 10^6$.

Translated by ChatGPT 5