#P7418. 枇杷树
枇杷树
枇杷树
题目背景
杨吞天家有个很大的后院,但是光秃秃的,看起来很是荒凉。杨吞天决定种一个枇杷树种子。许多年后,杨吞天的后院已经长满了“亭亭如盖”的枇杷树。
题目描述
杨吞天观察了枇杷树林的生长规律,他惊奇地发现,每一棵长出的枇杷树和之前长出的枇杷树有着令人惊奇的相似性!
具体来说,每一年都会新长出一颗枇杷树,第 年长出的枇杷树记为。第 年长出来的枇杷树由于只是一个种子,因此它是一棵只有一个结点的树,该结点编号为。
对于每个,都可以用 个参数来描述它,。表示将 的 号结点和 的 号结点用一条长度为 的边连结起来得到了(注意, 可以等于,生成新树时使用两棵树各自的一份副本,即使 ,两份副本的节点也互不相同)。
杨吞天将每年的树上的结点进行了重新编号,具体来说:对于第年长出来的枇杷树,在第棵树中点的编号不会变,在 棵树中的点的编号加上第棵树的大小作为新的编号。 杨吞天很喜欢吃枇杷,每棵树上的每个结点都有一个枇杷。他想知道每棵树上任意两个枇杷间的距离之和。形式化地,对于每一棵树,你需要求
$\sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} \operatorname{dis} \left( i , j \right) .$
其中为树的结点个数, 为结点两个结点的简单路径上的边的长度和,注意结点从开始编号。
由于答案可能很大,你只需要输出答案对 取模的结果就可以了。
输入格式
从标准输入读入。
输入共若干行。
第一行一个正整数,表示有 年。
接下来 行,每行 个非负整数 描述。
输出格式
向标准输出写出。
输出一共行,每行一个非负整数,第行的输出表示 对应的答案对 取模的结果。
样例1输入
4
0 0 0 0 3
1 0 1 0 4
2 1 0 1 5
1 1 0 0 2
样例1输出
3
14
76
26
测试点约束
对于所有测试点,满足 $1\le m\le 300,0\le x_{i},y_{i}<i,1\le w_{i}\le 10^{9},0\le u_{i},v_{i}\le 10^{18}$,保证每棵树的节点数不超过 ,并且 ,,所给节点编号有效。
每个子任务的具体限制见下表:
| 子任务编号 | 分值 | 特殊限制 |
|---|---|---|
| 1 | 10 | |
| 2 | 每棵树的大小都不超过 | |
| 3 | 树的形态总是链 | |
| 4 | 无 |