Ruri Loves Maschera
题目背景
琉璃最近沉迷于《Maschera》的二次创作。
题目描述
琉璃小说中的世界有 $n$ 座城市,其中有 $n-1$ 条道路,不包含重边、自环。这 $n-1$ 条道路中,第 $i$ 条道路的魔力值为 $w_i$。
琉璃作为夜魔女王,她决定要观光整个黑暗世界 。她每次会随机选一个城市为起点,经过不少于 $L$ 条且不多于 $R$ 条道路后在一个城市为终点结束。**她在观光的时候是不走回头路的。**若琉璃每次观光中经过道路的魔力值依次为 $v_1,v_2,...,v_k(L\leq k\leq R)$,那么她会获得 $\max(v_1,v_2,...,v_k)$ 的魔力值。
现在琉璃想知道,她尝试了所有合法的观光路线后,她所获得的魔力值总和为多少。
**注意,$x$ 到 $y$ 的路径和 $y$ 到 $x$ 的路径视为两条路径。**
输入输出格式
输入格式
第一行三个数 $n,L,R$
接下来 $n-1$ 行,每行三个数 $x,y,w$,表示 $x$ 结点和 $y$ 结点之间有一条魔力值为 $w$ 的道路。
输出格式
输出她所获得的魔力值总和。
输入输出样例
输入样例 #1
5 2 3
1 2 2
2 3 2
3 4 4
4 5 5
输出样例 #1
40
说明
数据范围:
对于 $10\%$ 的数据,$n\leq 5000$
另有 $10\%$ 的数据,$\min(x,y)=1$
另有 $15\%$ 的数据,$|x-y|=1$
另有 $25\%$ 的数据,$L=1,R=n-1$
对于 $100\%$ 的数据,$n\leq 10^5,1\leq L\leq R\leq n-1,1\leq w_i\leq 10^5$