CGY 要暂时离开 301 了,301 种有一颗小树苗,SLF 和 LXY 觉得应该为 CGY 留个纪念,于是就把这颗树叫做 CGY 树。
CGY 树有 N 个结点,结点编号依次为 1 到 N,每条边都有一个权值 L。其中 CGY 树会有一个 1 到 N 的排列。
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 |
提示
对于样例中的第一组数据:
所以 CGY 树所有可能的幸运值之和为 2+3+3+3+3+2=16
来源
2019 欢送 (迫害) CGY 杯程序设计竞赛