#P7418. 枇杷树

    ID: 7432 传统题 1000ms 512MiB 尝试: 3 已通过: 2 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划DAG 动态规划组合数学贡献法数据结构离线预收集坐标排序与序列处理离散化CF2400

枇杷树

枇杷树

题目背景

杨吞天家有个很大的后院,但是光秃秃的,看起来很是荒凉。杨吞天决定种一个枇杷树种子。许多年后,杨吞天的后院已经长满了“亭亭如盖”的枇杷树。

题目描述

杨吞天观察了枇杷树林的生长规律,他惊奇地发现,每一棵长出的枇杷树和之前长出的枇杷树有着令人惊奇的相似性!

具体来说,每一年都会新长出一颗枇杷树,第 ii 年长出的枇杷树记为TiT_{i}。第00 年长出来的枇杷树T0T_{0}由于只是一个种子,因此它是一棵只有一个结点的树,该结点编号为00。

对于每个Ti(i>0)T_{i}(i>0),都可以用 55 个参数来描述它,xi,yi,ui,vi,wi(xi,yi<i)x_{i},y_{i},u_{i},v_{i},w_{i}(x_{i},y_{i}<i)。表示将 TxiT_{x_{i}} 的uiu_{i} 号结点和TyiT_{y_{i}} 的viv_{i} 号结点用一条长度为wiw_{i} 的边连结起来得到了TiT_{i}(注意,xix_{i} 可以等于yiy_{i},生成新树时使用两棵树各自的一份副本,即使 xi=yix_i=y_i,两份副本的节点也互不相同)。

杨吞天将每年的树上的结点进行了重新编号,具体来说:对于第ii年长出来的枇杷树,在第xix_{i}棵树中点的编号不会变,在yiy_{i} 棵树中的点的编号加上第xix_{i}棵树的大小作为新的编号。 杨吞天很喜欢吃枇杷,每棵树上的每个结点都有一个枇杷。他想知道每棵树上任意两个枇杷间的距离之和。形式化地,对于每一棵树,你需要求

$\sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} \operatorname{dis} \left( i , j \right) .$

其中nn为树的结点个数,dis(i,j)dis(i,j) 为结点i,ji,j两个结点的简单路径上的边的长度和,注意结点从00开始编号。

由于答案可能很大,你只需要输出答案对 109+710^{9}+7取模的结果就可以了。

输入格式

从标准输入读入。

输入共若干行。

第一行一个正整数mm,表示有mm 年。

接下来mm 行,每行55 个非负整数xi,yi,ui,vi,wix_{i},y_{i},u_{i},v_{i},w_{i} 描述TiT_{i}。

输出格式

向标准输出写出。

输出一共mm行,每行一个非负整数,第ii行的输出表示TiT_{i} 对应的答案对 109+710^{9}+7 取模的结果。

样例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}$,保证每棵树的节点数不超过 2×10182\times10^{18},并且 0≤ui<∣Txi∣0\le u_i<|T_{x_i}|,0≤vi<∣Tyi∣0\le v_i<|T_{y_i}|,所给节点编号有效。

每个子任务的具体限制见下表:

子任务编号 分值 特殊限制
1 10 m≤10m\le 10
2 2020 每棵树的大小都不超过 10510^{5}
3 树的形态总是链
4 5050 无