P5351 Ruri Loves Maschera

Ruri has recently become obsessed with fan creations of *Maschera*.

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.**

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 the total sum of the magic values she gains.

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