1460. CGY 树

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

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

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

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

输入

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

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

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

N-1 行中每行有三个整数 X,Y,L,以空格隔开,代表结点 X 到结点 Y 有一条边,边的长度为 L。数据保证 1\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

提示

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

  • 123 排列的幸运值为:1+1 = 2
  • 132 排列的幸运值为:2+1 = 3
  • 213 排列的幸运值为:1+2 = 3
  • 231 排列的幸运值为:1+2 = 3
  • 312 排列的幸运值为:2+1 = 3
  • 321 排列的幸运值为:1+1 = 2

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

来源

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

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