Sum of Maximum Magic in Tourist Routes

In the world of Liuli novels, there are \( n \) cities connected by \( n-1 \) roads forming a tree (i.e. there are no multi-edges or self-loops). The \( i\)-th road has a magic value \( w_i \). As the Queen of Night Demons, Liuli wishes to tour this dark world. During each tour, she randomly chooses a starting city and travels along a simple path (i.e. she never revisits an edge) such that the number of roads she passes is at least \( L \) and at most \( R \). If the magic values of the roads she traverses are \( v_1,v_2,\dots,v_k \) (with \( L\le k\le R \)), she obtains a magic power equal to \( \max(v_1,v_2,\dots,v_k) \). Note that the path from city \( x \) to city \( y \) is considered different from the path from city \( y \) to city \( x \).

Your task is to compute the sum of magic power obtained over all valid tourist routes.

Input/Output Format:

The input begins with three integers \( n,L,R \) on the first line. The next \( n-1 \) lines each contain three integers \( u, v, w \) representing a road between cities \( u \) and \( v \) with magic value \( w \).

The output is a single integer, the total sum of magic power acquired. All formulas are in \( \LaTeX \) format.

inputFormat

The first line contains three integers \( n \), \( L \), and \( R \) where \( n \) is the number of cities and \( L \) and \( R \) are the minimum and maximum number of roads Liuli must traverse during each tour.

Each of the following \( n-1 \) lines contains three integers \( u \), \( v \), and \( w \), indicating that there is a road connecting city \( u \) and city \( v \) with a magic value of \( w \).

It is guaranteed that the given graph is a tree (i.e. connected and acyclic).

outputFormat

Output a single integer representing the sum of magic power obtained over all valid routes.

sample

3 1 2
1 2 3
2 3 2

16