CGY 要暂时离开 301 了,301 种有一颗小树苗,SLF 和 LXY 觉得应该为 CGY 留个纪念,于是就把这颗树叫做 CGY 树。
CGY 树有 个结点,结点编号依次为 到 ,每条边都有一个权值 。其中 CGY 树会有一个 到 的排列。
CGY 给这颗树定义了一个的幸运值。幸运值计算规则如下:CGY 树的排列中,每个数字代表相应的结点。幸运值就等于排列中所有相邻的两个结点最短距离之和。例如 且一个排列为 ,则幸运值为 。
现在,CGY 想知道 CGY 树所有可能的幸运值之和是多少?答案对 取模。
输入
输入有多组数据(数据保证最多只有 组数据),以 EOF 作为结束标志。
每组数据的第一行为一个整数 ,代表 CGY 树的结点数。
接下来 行,描述 CGY 树的边。
行中每行有三个整数 ,以空格隔开,代表结点 到结点 有一条边,边的长度为 。数据保证 。
输出
输出一个整数,代表 CGY 树所有可能的幸运值之和
样例
标准输入 复制文本 |
3 1 2 1 2 3 1 3 1 2 1 1 3 2 |
标准输出 复制文本 |
16 24 |
提示
对于样例中的第一组数据:
所以 CGY 树所有可能的幸运值之和为
来源
2019 欢送 (迫害) CGY 杯程序设计竞赛