当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

5401:Persistent Link/cut Tree

题目描述
Teacher Mai has $m+1$ trees, $T_0,T_1,\cdots,T_m$. $T_0$ consists one vertex numbered $0$.

He generated the $T_i$ in this way. Get a copy of $T_{a_i}$ and $T_{b_i}$. Add an edge with length $l_i$ between vertex numbered $c_i$ in $T'_{a_i}$ and $d_i$ in $T'_{b_i}$. Relabel the vertices in the new tree. Let $k$ be the number of vertices in $T'_{a_i}$. He keeps labels of vertices in $T'_{a_i}$ the same, and adds $k$ to labels of vertices in $T'_{b_i}$.

If there is a tree $T$ with $n$ vertices $v_0,v_1,v_2,\cdots,v_{n-1}$, $F(T)=\sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} d(v_i,v_j)$($d(v_i,v_j)$ means the distance between the $v_i$ and $v_j$).

For every $i(1\leq i\leq m)$, he wants to know $F(T_i)$.
输入解释
There are multiple test cases(about $100$).

For each test case, the first line contains one number $m(1\leq m\leq 60)$, the following are $m$ lines. The $i$-th lines contains five numbers $a_i,b_i,c_i,d_i,l_i(0\leq a_i,b_i<i,0\leq l_i\leq 10^9)$. It's guarenteed that there exists a vertex numbered $c_i$ in $T_{a_i}$ and there exists a vertex numbered $d_i$ in $T_{b_i}$.
输出解释
For each test case, print $F(T_i)$ modulo $10^9+7$ in the $i$-th line.
输入样例
3
0 0 0 0 2
1 1 0 0 4
2 2 1 0 3
输出样例
2
28
216
来自杭电HDUOJ的附加信息
Author xudyh
Recommend wange2014

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-5401

最后修改于 2020-10-25T23:22:22+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 65536/65536K(Java/Others)