這題我的作法根官方解只有後半部不一樣，就是在算答案的那部份。前面幾步一樣就是當我們要處理連續的好幾個詢問時，把整棵樹重建（因為可能有一些點被拔到其他地方了），先把那些重要的點找出來，之後叫他們黑點，其餘的則為白點。並且把黑點構成的樹建出來，稱他為新樹，原本題目給的則為原樹。我們要維護的值有兩個東西，就如官方解裡寫的path值和ch值。首先看如何求path值，令d[x]=(size[fa[x]]-size[x])\cdot val[fa[x]]，其中size[x]為x（在原樹）子樹的大小，fa[x]則代表x在原樹的父節點，val[]則是那個節點上標的值，則x的path值就是由x開始一路往上走，走到1之前把所有的節點的d值加起來（對了，我還有多把1標成黑點，這樣新樹的根也是1了，不用再區分）。由這件事就可以得到path值的算法：如果對每條新樹中的邊都紀錄這條邊上經過的所有點的d值總和，那麼一個黑點的path值就可以一路沿著祖先的邊走上去並加總得到了。具體來說，假設x\rightarrow y是新樹中的一條父親指向孩子的邊，並且令y沿著原樹的父親走上去經過的路徑為y=s_1,...,s_{r-1},s_r=x，那麼就讓x\rightarrow y這條邊上紀錄的值等於d[s_1]+...+d[s_{r-1}]（之後叫他dsum值）。
再來則是ch值（在我的code裡是叫作pnum），對於原樹中的一個點x，容易得出他的ch值會等於\displaystyle size[x]^2-(\sum_{i}size[i]^2)，其中i跑遍所有x的子節點。在建圖的時候可以先對原樹DFS一次，求出每個點的ch值，重點是當我們把一個點拔掉和接回去的時候要如何更新每個黑點的ch值。如果每次操作完都重新算一次所有黑點的ch值的話複雜度會是好的（黑位黑點不多），但不能重算所有黑白點的，因此只能對新樹DFS一次。所以就可以得到對於每條x\rightarrow y的邊，我們必須紀錄size[s_{r-1}]是多少（s_i同上面的記號）（之後叫他這條邊的ssz值），這樣才能在新樹中DFS時算出每個黑點的ch值。因此每條新樹中的邊會紀錄dsum值和ssz值。但光這樣還不夠算出黑點的ch值，因為在原樹中有可能黑點有一個子樹是全部都是白的，我們當然也要知道他的大小的平方和，因此對每個黑點x還要紀錄一個值sz2sum，代表：若t_1,...,t_z為x在原樹中所有全白子樹們的大小，則其為t_1^2+...+t_z^2，這樣就能在重新DFS時算出每個點的ch值了。
整理一下上面的算法，在處理每次詢問時我們要維護好的值有：每條新樹邊上的dsum值、ssz值，還有每個黑點的size值、val值（這兩個在維護前面那些東西時會需要）、sz2sum值、新樹中的父節點、pnum值（這是在詢問結束後再對新樹DFS計算）。當拔掉一個節點y的子樹時，會影響到的東西有：從y沿著新樹邊走上去的所有邊上的兩個值，和路上經過節點的size值，並且要記得順便計算y的path值是多少。那些數的變動值不難由定義得出，這邊就省略。在接回去的時候影響到的東西也是那些，所以照做一次就可以了，而在接上去時這條新產生的邊的dsum值和ssz值顯然分別會是d[y]和size[y]。最後記得再DFS一次求pnum。至於此次詢問是改一個點x的值的話，會影響到的則是所有x連到他孩子的邊上的dsum值，變動大小也不難推出。
這樣傳上去之後WA第三筆，我辛苦的把他的樹畫出來模擬後發現我漏了好幾個很容易忘記的東西，一個是當我們拔去y所在的子樹時，記y的父親為f，那麼f的sz2sum值必須要增加！因為此時f多了一棵全白的子樹，他原本是用來連接y的，現在y沒了當然要加回他的sz2sum中。另外則是我在DFS計算pnum值的時候，如果此時這個點是新樹的葉節點，那麼就直接 return （因為在原樹建完，處理詢問之前會有一次DFS，把每個黑點的pnum值都算好了，而在新樹中的葉節點的pnum值顯然在這好幾次詢問中都會保持相同）。這樣會有個很不明顯的問題，就是有可能一個黑點在新樹中的子節點都被拔光了，自己成為了葉節點，那麼在算他的pnum值就直接 return 了，這不是我們想要的。解決這個問題的方法就是當我們發現把一個點拔掉之後會讓他父親成為葉節點時，就趕快把他的pnum值算好就好了（其實就是size值平方扣掉sz2sum值）。
code :
#include<bits/stdc++.h> #define DB double #define LL long long using namespace std; const int maxn=50000+10 ; struct query{int type,x,y;}qu[maxn]; int n,fa[maxn] ; LL val[maxn],sz[maxn] ; vector<int> v[maxn] ; bool mark[maxn],have[maxn] ; LL d[maxn] ; /// d[x] = (size[fa[x]]-size[x]) * val[fa[x]] int dfs(int x) { sz[x]=1 ; int ret=0 ; for(auto i : v[x]) ret+=dfs(i) , sz[x]+=sz[i] ; for(auto i : v[x]) d[i]=(sz[x]-sz[i])*val[x] ; have[x]=( (ret||mark[x]) ? 1 : 0 ) ; if(ret>=2 || mark[x]) {mark[x]=1 ; return 1 ;} else return ret ; } struct P{int to ; LL ssz,dsum;}; /// son's size & sum of d[i] on the path vector<P> v2[maxn] ; /// new tree int fa2[maxn] ; /// sz2sum[x] = sum_{i is son of x && have[i]==0} sz[i]^2 LL sz2sum[maxn] ; LL pnum[maxn] ; /// how many pairs of node whose LCA = x void dfs2(int x,bool isfir=0) { if(v2[x].empty()) { if(!isfir) return ; pnum[x]=sz[x]*sz[x] ; for(auto i : v[x]) pnum[x]-=sz[i]*sz[i] ; return ; } pnum[x]=sz[x]*sz[x]-sz2sum[x] ; for(auto i : v2[x]) dfs2(i.to,isfir) , pnum[x]-=i.ssz*i.ssz ; } int getid(int x,int y) { for(int i=0;;i++) if(v2[x][i].to==y) return i ; } void build_graph(int num) { fill(mark,mark+n+1,0) ; fill(have,have+n+1,0) ; for(int i=1;i<=n;i++) v[i].clear() , v2[i].clear() ; for(int i=2;i<=n;i++) v[fa[i]].push_back(i) ; for(int i=0;i<num;i++) { mark[qu[i].x]=1 ; if(qu[i].type==1) mark[qu[i].y]=1 ; } mark[1]=1 ; dfs(1) ; /// 1 is root of new tree for(int i=1;i<=n;i++) if(mark[i]) { sz2sum[i]=0 ; for(auto j : v[i]) if(!have[j]) sz2sum[i]+=sz[j]*sz[j] ; if(i==1) continue ; int j ; LL ssz=0LL,dsum=0LL ; for(j=i;;j=fa[j]) { dsum+=d[j] ; if(mark[fa[j]]) break ; } ssz=sz[j] ; j=fa[j] ; v2[j].push_back((P){i,ssz,dsum}) ; fa2[i]=j ; } } LL nowans ; void process_query(int qid) { if(qu[qid].type==2) { int x=qu[qid].x , nval=qu[qid].y ; nowans+=pnum[x]*(nval-val[x]) ; for(auto &i : v2[x]) i.dsum+=(sz[x]-i.ssz)*(nval-val[x]) ; val[x]=nval ; printf("%.15f\n",((DB)nowans)/n/n) ; return ; } int x=qu[qid].y , y=qu[qid].x , id ; for(int i=x;i!=1;i=fa2[i]) if(i==y || y==1) {swap(x,y) ; break ;} fa[y]=x ; LL dif=0LL ; for(int i=y;i!=1;i=fa2[i]) /// update dsum and ssz value of needed edge after { /// removing the subtree rooted at y , and calculate answer sz[fa2[i]]-=sz[y] ; for(auto &k : v2[fa2[i]]) if(k.to!=i) k.dsum-=val[fa2[i]]*sz[y] ; else dif-=k.dsum , k.ssz-=sz[y] ; } int f=fa2[y] ; P &e=v2[f][getid(f,y)] ; sz2sum[f]+=e.ssz*e.ssz ; swap(e,v2[f].back()) ; v2[f].pop_back() ; v2[x].push_back((P){y,0,val[x]*sz[x]}) ; fa2[y]=x ; if(v2[f].empty()) pnum[f]=sz[f]*sz[f]-sz2sum[f] ; /// !!!!!!!!!!!!!!!!!!! for(int i=y;i!=1;i=fa2[i]) /// update dsum ans ssz value of needed edge after { /// linking the subtree rooted at y to x , and calculate answer sz[fa2[i]]+=sz[y] ; for(auto &k : v2[fa2[i]]) if(k.to!=i) k.dsum+=val[fa2[i]]*sz[y] ; else dif+=k.dsum , k.ssz+=sz[y] ; } nowans+=2*dif*sz[y] ; printf("%.15f\n",((DB)nowans)/n/n) ; dfs2(1) ; /// update pnum } bool first=1 ; void process(int num) { build_graph(num) ; nowans=0LL ; for(int i=1;i<=n;i++) { LL add=sz[i]*sz[i] ; for(auto j : v[i]) add-=sz[j]*sz[j] ; nowans+=add*val[i] ; } if(first) printf("%.15f\n",((DB)nowans)/n/n) , first=0 ; dfs2(1,1) ; /// calculate pnum for(int i=0;i<num;i++) process_query(i) ; } main() { scanf("%d",&n) ; fa[1]=1 ; for(int i=2;i<=n;i++) scanf("%d",&fa[i]) ; for(int i=1;i<=n;i++) scanf("%lld",&val[i]) ; int Q ; scanf("%d",&Q) ; int sq=(int)sqrt(Q+0.5) ; for(int i=0;i<Q;i++) { char c[5] ; scanf("%s%d%d",c,&qu[i%sq].x,&qu[i%sq].y) ; qu[i%sq].type=(c[0]=='P' ? 1 : 2) ; if((i%sq)==sq-1 || i==Q-1) process(i%sq+1) ; } }
沒有留言:
張貼留言