Description
再過三個多月就是圣誕節了，小R 想送小Y 一棵圣誕樹作為節日禮物。因為他想讓這棵圣誕樹越大越好，所以當然是買不到能夠讓他滿意的樹的，因此他打算自己把這棵樹拼出來。
現在，小R 開始畫這棵樹的設計圖紙了。因為這棵樹實在太大，所以他采用了一種比較方便的方法。首先他定義了m+ 1 棵樹T0 到Tm。最開始他只畫好了T0 的圖紙：就只有一個點，編號為0。
接著，對于每一棵樹Ti，他在第Tai 棵樹的第ci 個點和第Tbi 棵樹的第di 個點之間連上了一條長度為li 的邊。在Ti 中，他保持Tai 中的所有節點編號不變，然后如果Tai 中有s 個節點，他會把Tbi 中的所有節點的編號加上s。
終于，他畫好了所有的樹。現在他定義一顆大小為n 的樹的美觀度為
,其中d(i; j) 為這棵樹中i 到j 的最短距離。
為了方便小R 選擇等究竟拼哪一棵樹，你可以分別告訴他T1 到Tm 的美觀度嗎？答案可能很大，請對10^9 + 7 取模后輸出。
現在，小R 開始畫這棵樹的設計圖紙了。因為這棵樹實在太大，所以他采用了一種比較方便的方法。首先他定義了m+ 1 棵樹T0 到Tm。最開始他只畫好了T0 的圖紙：就只有一個點，編號為0。
接著，對于每一棵樹Ti，他在第Tai 棵樹的第ci 個點和第Tbi 棵樹的第di 個點之間連上了一條長度為li 的邊。在Ti 中，他保持Tai 中的所有節點編號不變，然后如果Tai 中有s 個節點，他會把Tbi 中的所有節點的編號加上s。
終于，他畫好了所有的樹。現在他定義一顆大小為n 的樹的美觀度為
,其中d(i; j) 為這棵樹中i 到j 的最短距離。為了方便小R 選擇等究竟拼哪一棵樹，你可以分別告訴他T1 到Tm 的美觀度嗎？答案可能很大，請對10^9 + 7 取模后輸出。
Input
第一行輸入一個正整數T 表示數據組數。每組數據的第一行是一個整數m，接下來m 行每行五個整數ai, bi, ci, di, li，保證0 <= ai, bi < i， 0<= li<= 10^9，ci, di 存在。
Output
對于每組詢問輸出m 行。第i 行輸出Ti 的權值
Sample Input
1
2
0?0 0 0 2
1 1 0 0 4
Sample Output
2
28
Data Constraint
對于30% 的數據，m <= 8
對于60% 的數據，m <= 16
對于100% 的數據，1 <= m<= 60，T<= 100
對于60% 的數據，m <= 16
對于100% 的數據，1 <= m<= 60，T<= 100
?
題解
- 題目大意：給定了n棵樹，每次會獎兩棵樹中的x，y之間連一條len的邊，也就是將兩棵樹合并，問每棵樹上兩兩點對的最短路徑和
- 設calc1(x,y)為x這棵樹里，其他點到y的最短路徑和，calc2(x,y,k)為x這棵樹里，y到k的最短路徑長度
- 設f[i]為第i棵數的答案，f[i]=f[i.left]+f[i.right]+calc1(i.left,i.c)*i.right.size+calc1(i.right,i.d)*i.left.size+i.len*i.left.size*i.right.size
- calc1(x,y)中可以分成兩種情況，①在x的左子樹②在x的右子樹
- 當在x的左子樹時calc1(x,y)=calc1(x.left,y)+(calc2(y,x.left,x.c)+x.len)*x.right.size+calc1(x.right,x.d)，但在右子樹里也是同理
- calc2(x,y,z)也可以想上面分成兩種情況，①y和k在同一棵子樹里②y和k不在同一棵子樹里
- 當在它們在同一顆子樹里，直接往下遞歸；當它們不在同一棵子樹里時，calc2(x,y,z)=calc2(x.left,y,x.c)+calc2(x.right,z,x.d)+x.len
- 這題比較惡心，還要用map優化
代碼
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<map> 5 #define ll long long 6 using namespace std; 7 const ll N=70,mo=1e9+7; 8 ll T,n,f[N]; 9 typedef pair<ll,ll> node; 10 struct edge{ ll a,b,size,c,d,v; }p[N]; 11 map <node,ll> Q[N]; 12 ll calc2(ll k,ll x,ll y) 13 { 14 if (x>y) swap(x,y); 15 if (k==0||x==y) return 0; 16 if (x<p[p[k].a].size&&y<p[p[k].a].size) return calc2(p[k].a,x,y); 17 else if (x>=p[p[k].a].size&&y>=p[p[k].a].size) return calc2(p[k].b,x-p[p[k].a].size,y-p[p[k].a].size); 18 else 19 { 20 node q=make_pair(x,y); 21 if (Q[k].find(q)!=Q[k].end()) return Q[k][q]; 22 return Q[k][q]=(calc2(p[k].a,p[k].c,x)+calc2(p[k].b,p[k].d,y-p[p[k].a].size)+p[k].v)%mo; 23 } 24 } 25 ll calc1(ll k,ll x) 26 { 27 ll r=0; node q=make_pair(x,0); 28 if (Q[k].find(q)!=Q[k].end()) return Q[k][q]; 29 if (k==0) return 0; 30 if (x<p[p[k].a].size) r=(calc1(p[k].a,x)+calc1(p[k].b,p[k].d))%mo+(((p[k].v+calc2(p[k].a,p[k].c,x))%mo)*(p[p[k].b].size%mo))%mo; 31 else r=(calc1(p[k].a,p[k].c)+calc1(p[k].b,x-p[p[k].a].size))%mo+(((p[k].v+calc2(p[k].b,p[k].d,x-p[p[k].a].size))%mo)*(p[p[k].a].size%mo)%mo); 32 return (Q[k][q]=r)%mo; 33 } 34 int main() 35 { 36 freopen("data.in","r",stdin); 37 scanf("%d",&T); 38 while (T--) 39 { 40 scanf("%d",&n),memset(p,0,sizeof(p)),p[0].size=1; 41 for (int i=1;i<=n;i++) scanf("%lld%lld%lld%lld%lld",&p[i].a,&p[i].b,&p[i].c,&p[i].d,&p[i].v),p[i].size=p[p[i].a].size+p[p[i].b].size,Q[i].clear(); 42 for (int i=1;i<=n;i++) 43 f[i]=((f[p[i].a]+f[p[i].b])%mo+(calc1(p[i].a,p[i].c)*(p[p[i].b].size%mo)+(calc1(p[i].b,p[i].d)*(p[p[i].a].size%mo))%mo 44 +(((p[i].v%mo)*(p[p[i].a].size%mo))%mo*(p[p[i].b].size%mo))%mo)%mo)%mo, 45 printf("%lld\n",f[i]); 46 } 47 }
?
