欢迎加入2019年新生赛官方群725273468

Persistent Link/cut Tree

Time Limit
1s
Memory Limit
65536KB
Judge Program
Standard
Ratio(Solve/Submit)
0.00%(0/2)
Description:

Teacher Mai has m+1 trees, T0,T1,⋯,TmT0 consists one vertex numbered 0.

He generated the Ti in this way. Get a copy of Tai and Tbi. Add an edge with length li between vertex numbered ci in T′ai and di in T′bi. Relabel the vertices in the new tree. Let k be the number of vertices in T′ai. He keeps labels of vertices in T′ai the same, and adds k to labels of vertices in T′bi.

If there is a tree T with n vertices v0,v1,v2,⋯,vn−1F(T)=∑n−1i=0∑n−1j=i+1d(vi,vj)(d(vi,vj) means the distance between the vi and vj).

For every i(1≤i≤m), he wants to know F(Ti).

Input:

There are multiple test cases(about 100).

For each test case, the first line contains one number m(1≤m≤60), the following are m lines. The i-th lines contains five numbers ai,bi,ci,di,li(0≤ai,bi<i,0≤li≤109). It's guarenteed that there exists a vertex numbered ci in Tai and there exists a vertex numbered di in Tbi.

Output:

For each test case, print F(Ti) modulo 109+7 in the i-th line.

Sample Input:
3
0 0 0 0 2
1 1 0 0 4
2 2 1 0 3
Sample Output:
2
28
216
Source:

2015 Multi-University Training Contest 9


Submit