1460. CGY 树

CGY 要暂时离开 301 了,301 种有一颗小树苗,SLF 和 LXY 觉得应该为 CGY 留个纪念,于是就把这颗树叫做 CGY 树。

CGY 树有 NN 个结点,结点编号依次为 11NN,每条边都有一个权值 LL。其中 CGY 树会有一个 11NN 的排列。

CGY 给这颗树定义了一个的幸运值。幸运值计算规则如下:CGY 树的排列中,每个数字代表相应的结点。幸运值就等于排列中所有相邻的两个结点最短距离之和。例如 N=4N=4 且一个排列为 42314231,则幸运值为 dis(4,2)+dis(2,3)+dis(3,1)dis(4,2)+dis(2,3)+dis(3,1)

现在,CGY 想知道 CGY 树所有可能的幸运值之和是多少?答案对 109+710^9+7 取模。

输入

输入有多组数据(数据保证最多只有 1010 组数据),以 EOF 作为结束标志。

每组数据的第一行为一个整数 N (1N105)N\ (1\leq N \leq 10^5),代表 CGY 树的结点数。

接下来 N1N-1 行,描述 CGY 树的边。

N1N-1 行中每行有三个整数 X,Y,LX,Y,L,以空格隔开,代表结点 XX 到结点 YY 有一条边,边的长度为 LL。数据保证 1X,YN1L1091\leq X,Y \leq N,1\leq L\leq 10^9

输出

输出一个整数,代表 CGY 树所有可能的幸运值之和

样例

标准输入 复制文本
3
1 2 1
2 3 1
3
1 2 1
1 3 2
标准输出 复制文本
16
24

提示

对于样例中的第一组数据:

  • 123123 排列的幸运值为:1+1=21+1 = 2
  • 132132 排列的幸运值为:2+1=32+1 = 3
  • 213213 排列的幸运值为:1+2=31+2 = 3
  • 231231 排列的幸运值为:1+2=31+2 = 3
  • 312312 排列的幸运值为:2+1=32+1 = 3
  • 321321 排列的幸运值为:1+1=21+1 = 2

所以 CGY 树所有可能的幸运值之和为 2+3+3+3+3+2=162+3+3+3+3+2=16

来源

2019 欢送 (迫害) CGY 杯程序设计竞赛

登录以提交代码。
单点时限 2 秒
内存限制 512 MB
提交 17
通过 5