JZOJ 4211. 【五校聯考1day2】送你一顆聖誕樹（分治）

JZOJ 4211. 【五校聯考1day2】送你一顆聖誕樹

題目

Description

再過三個多月就是聖誕節了，小R想送小Y一棵聖誕樹作為節日禮物。因為他想讓這棵聖誕樹越大越好，是以當然是買不到能夠讓他滿意的樹的，是以他打算自己把這棵樹拼出來。

現在，小R開始畫這棵樹的設計圖紙了。因為這棵樹實在太大，是以他采用了一種比較友善的方法。首先他定義了 m + 1 m+ 1 m+1棵樹 T 0 T0 T0到 T m Tm Tm。最開始他隻畫好了 T 0 T0 T0 的圖紙：就隻有一個點，編号為0。

接着，對于每一棵樹 T i Ti Ti，他在 T a i Tai Tai的第 c i ci ci個點和 T b i Tbi Tbi的第 d i di di個點之間連上了一條長度為 l i li li的邊。在 T i Ti Ti中，他保持 T a i Tai Tai中的所有節點編号不變，然後如果 T a i Tai Tai中有 s s s個節點，他會把 T b i Tbi Tbi中的所有節點的編号加上 s s s。

終于，他畫好了所有的樹。現在他定義一顆大小為n 的樹的美觀度為

其中 d ( i , j ) d(i,j) d(i,j) 為這棵樹中i 到j 的最短距離。

為了友善小R選擇等究竟拼哪一棵樹，你可以分别告訴他 T 1 T1 T1到 T m Tm Tm的美觀度嗎？答案可能很大，請對 1 0 9 + 7 10^9 + 7 109+7取模後輸出。

Input

第一行輸入一個正整數 T T T 表示資料組數。每組資料的第一行是一個整數 m m m，接下來 m m m行每行五個整 a i , b i , c i , d i , l i ai, bi, ci, di, li ai,bi,ci,di,li，保證 0 ≤ a i , b i < i 0≤ai, bi < i 0≤ai,bi<i， 0 ≤ l i ≤ 1 0 9 0≤li≤10^9 0≤li≤109， c i , d i ci, di ci,di存在。

Output

對于每組詢問輸出 m m m行。第 i i i行輸出 T i Ti Ti的權值

Sample Input

1

2

0 0 0 0 2

1 1 0 0 4

Sample Output

2

28

Data Constraint

對于30%的資料， m ≤ 8 m≤8 m≤8

對于60% 的資料， m ≤ 16 m≤16 m≤16

對于100% 的資料， 1 ≤ m ≤ 60 1≤m≤60 1≤m≤60， T ≤ 100 T≤100 T≤100

題解

• 點數到最後可能會有 2 60 2^{60} 260個，會很大，不可能每個都存下來。
• 隻考慮怎麼計算要求的答案就好。
• 對于每一棵（題目寫的是“顆”）樹 i i i，記錄 e [ i ] . a ， e [ i ] . b ， e [ i ] . c ， e [ i ] . d ， e [ i ] . l e[i].a，e[i].b，e[i].c，e[i].d，e[i].l e[i].a，e[i].b，e[i].c，e[i].d，e[i].l如題目中的 a ， b ， c ， d ， l a，b，c，d，l a，b，c，d，l，記錄 e [ i ] . s e[i].s e[i].s表示樹的大小。為了友善計算，把節點編号統一 + 1 +1 +1。
• 易得 e [ i ] . s = e [ e [ i ] . a ] . s + e [ e [ i ] . b ] . s e[i].s=e[e[i].a].s+e[e[i].b].s e[i].s=e[e[i].a].s+e[e[i].b].s.
• 定義函數 a l l ( T , x ) all(T,x) all(T,x)表示 T T T樹上所有節點到 x x x節點的距離和（其中 x x x是在 T T T樹中的編号）。
• 定義函數 t o ( T , x , y ) to(T,x,y) to(T,x,y)表示 T T T樹上節點 x x x到節點 y y y的距離（其中 x , y x,y x,y都是 T T T樹中的編号）。
• 發現隻有這兩個函數，就可以計算出答案，而且這兩個函數可以通過自己不斷類似分治地求答案。
• 部分式子如下：
• 先令 a = e [ i ] . a ， b = e [ i ] . b ， c = e [ i ] . c ， d = e [ i ] . d a=e[i].a，b=e[i].b，c=e[i].c，d=e[i].d a=e[i].a，b=e[i].b，c=e[i].c，d=e[i].d，
• 那麼 a n s [ i ] = a n s [ a ] + a n s [ b ] + e [ a ] . s ∗ e [ b ] . s ∗ e [ i ] . l + e [ a ] . s ∗ a l l ( b , d ) + e [ b ] . s ∗ a l l ( a , c ) ans[i]=ans[a]+ans[b]+e[a].s*e[b].s*e[i].l+e[a].s*all(b,d)+e[b].s*all(a,c) ans[i]=ans[a]+ans[b]+e[a].s∗e[b].s∗e[i].l+e[a].s∗all(b,d)+e[b].s∗all(a,c).
• a l l ( T , x ) all(T,x) all(T,x)：
• 1、如果 e [ T ] . s = 1 e[T].s=1 e[T].s=1，傳回值為 0 0 0；
• 2、如果 x x x在左子樹上，傳回值為 a l l ( a , x ) + a l l ( b , d ) + e [ b ] . s ∗ ( e [ T ] . l + t o ( a , x , c ) ) all(a,x)+all(b,d)+e[b].s*(e[T].l+to(a,x,c)) all(a,x)+all(b,d)+e[b].s∗(e[T].l+to(a,x,c))；
• 3、如果 x x x在右子樹上，傳回值為 a l l ( b , x − e [ a ] . s ) + a l l ( a , c ) + e [ a ] . s ∗ ( e [ T ] . l + t o ( b , x − e [ a ] . s , d ) ) all(b,x-e[a].s)+all(a,c)+e[a].s*(e[T].l+to(b,x-e[a].s,d)) all(b,x−e[a].s)+all(a,c)+e[a].s∗(e[T].l+to(b,x−e[a].s,d))。（ x − e [ a ] . s x-e[a].s x−e[a].s是轉化為右子樹中的編号）
• t o ( T , x , y ) to(T,x,y) to(T,x,y)：保證 x ≤ y x≤y x≤y，
• 1、如果 x = y x=y x=y，傳回值為 0 0 0；
• 2、如果 x , y x,y x,y都在左子樹上，傳回值為 t o ( a , x , y ) to(a,x,y) to(a,x,y)；
• 3、如果 x , y x,y x,y都在右子樹上，傳回值為 t o ( b , x , y ) to(b,x,y) to(b,x,y)；
• 4、如果 x x x在左子樹上， y y y在右子樹上，傳回值為 t o ( a , x , c ) + e [ T ] . l + t o ( b , y − e [ a ] . s , d ) to(a,x,c)+e[T].l+to(b,y-e[a].s,d) to(a,x,c)+e[T].l+to(b,y−e[a].s,d)。（ y − e [ a ] . s y-e[a].s y−e[a].s是轉化為右子樹中的編号）
• 這樣就能解決 60 60 60分了。
• 因為有很多重複計算的，是以考慮記憶化，
• 但是函數帶的參數過大，需要用哈希表來存儲。
• 對于 a l l all all函數，存入 t ∗ x t*x t∗x，
• 對于 t o to to函數，存入 t ∗ x ∗ y t*x*y t∗x∗y，
• 模數取 2 ∗ 1 0 5 + 9 2*10^5+9 2∗105+9，哈希表大小 5 ∗ 1 0 5 5*10^5 5∗105即可。

• 記得每次計算都要模數，否則會出現負數，而且錯誤總是難以查出。

代碼

#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long 
#define md 1000000007
#define z 200009
LL m,tn;
struct node
{
	LL s,l,a,b,c,d;
}e[61];
LL ans[61];
struct
{
	LL u,v,s,t,id;
}hx[500010],hs[500010];
LL hash(LL t,LL v)
{
	LL x=(t%z)*(v%z)%z;
	while(hs[x].id==tn+1)
	{
		if(hs[x].t==t&&hs[x].v==v) return x;
		x++;		
		if(x>500000) x=1;
	}
	return -x;
}
LL haxi(LL t,LL u,LL v)
{
	LL x=(t%z)*(u%z)%z*(v%z)%z;
	while(hx[x].id==tn+1)	
	{
		if(hx[x].t==t&&hx[x].u==u&&hx[x].v==v) return x;
		x++;
		if(x>500000) x=1;
	}
	return -x;
}
LL to(LL t,LL u,LL v)
{
	LL ss=e[e[t].a].s,sum;
	LL hs1=haxi(t,u,v);
	if(hs1>0) return hx[hs1].s; 
	if(u>v) 
	{
		LL tp=u;u=v,v=tp;
	}
	if(u==v) return 0;
	if(v<=ss) sum=to(e[t].a,u,v);
	else if(u>ss) sum=to(e[t].b,u-ss,v-ss);
	else sum=(to(e[t].a,u,e[t].c)+to(e[t].b,v-ss,e[t].d)+e[t].l)%md;
	hx[-hs1].t=t;
	hx[-hs1].s=sum%md;
	hx[-hs1].u=u;
	hx[-hs1].v=v;
	hx[-hs1].id=tn+1;
	return sum;
}
LL all(LL t,LL v)
{
	LL ss=e[e[t].a].s,sum;
	LL hs1=hash(t,v);
	if(hs1>0) return hs[hs1].s;
	if(e[t].s==1) return 0;
	if(v<=ss) sum=(all(e[t].a,v)+all(e[t].b,e[t].d)+e[e[t].b].s%md*e[t].l%md+e[e[t].b].s%md*to(e[t].a,v,e[t].c)%md)%md;
	else sum=(all(e[t].b,v-ss)+all(e[t].a,e[t].c)+e[e[t].a].s%md*e[t].l%md+e[e[t].a].s%md*to(e[t].b,v-ss,e[t].d)%md)%md;
	hs[-hs1].t=t;
	hs[-hs1].s=sum%md;
	hs[-hs1].v=v;
	hs[-hs1].id=tn+1;
	return sum;
}
int main()
{
	scanf("%lld",&tn);
	while(tn--)
	{
		scanf("%lld",&m);
		e[0].s=1;
		LL a,b,c,d;
		for(LL i=1;i<=m;i++)
		{
			scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e[i].l);
			c++,d++;
			e[i].a=a,e[i].b=b,e[i].c=c,e[i].d=d;
			e[i].s=e[a].s+e[b].s;
			ans[i]=ans[a]+ans[b]+(e[a].s%md)*(e[b].s%md)%md*e[i].l%md+e[a].s%md*all(b,d)%md+e[b].s%md*all(a,c)%md;
			ans[i]%=md;
			printf("%lld\n",ans[i]);
		}
	}
	return 0;
}