這題我的作法根官方解只有後半部不一樣，就是在算答案的那部份。前面幾步一樣就是當我們要處理連續的好幾個詢問時，把整棵樹重建（因為可能有一些點被拔到其他地方了），先把那些重要的點找出來，之後叫他們黑點，其餘的則為白點。並且把黑點構成的樹建出來，稱他為新樹，原本題目給的則為原樹。我們要維護的值有兩個東西，就如官方解裡寫的$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) ; } }
沒有留言:
張貼留言