Description

The world in Ruri’s novel has $n$ cities and $n-1$ roads, with no multiple edges or self-loops. Among these $n-1$ roads, the magic value of the $i$-th road is $w_i$.

As the Queen of the Night Demons, Ruri decides to tour the entire dark world. Each time, she randomly chooses a city as the starting point, and ends at some city after passing through at least $L$ roads and at most $R$ roads. She never goes back along the same road during the tour. If the magic values of the roads she passes through in one tour are $v_1, v_2, ..., v_k$ $(L \leq k \leq R)$ in order, then she gains a magic value of $\max(v_1, v_2, ..., v_k)$.

Now Ruri wants to know: after trying all valid tour routes, what is the total sum of the magic values she gains?

Note that the path from $x$ to $y$ and the path from $y$ to $x$ are considered two different paths.

Input Format

The first line contains three integers $n, L, R$.

The next $n-1$ lines each contain three integers $x, y, w$, indicating that there is a road between node $x$ and node $y$ with magic value $w$.

Output Format

Output the total sum of the magic values she gains.

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

40

Hint

Constraints:

For $10\%$ of the testdata, $n \leq 5000$.

For another $10\%$ of the testdata, $\min(x, y) = 1$.

For another $15\%$ of the testdata, $|x - y| = 1$.

For another $25\%$ of the testdata, $L = 1, R = n - 1$.

For $100\%$ of the testdata, $n \leq 10^5$, $1 \leq L \leq R \leq n - 1$, and $1 \leq w_i \leq 10^5$.

Translated by ChatGPT 5