顯然資源集合處就是樹(shù)的重心，這題需要?jiǎng)討B(tài)維護(hù)樹(shù)的重心。

每個(gè)連通塊以重心為根，用link-cut tree維護(hù)每個(gè)點(diǎn)的子樹(shù)大小以及子樹(shù)內(nèi)所有點(diǎn)到它的距離和。

合并兩個(gè)連通塊時(shí)，考慮啟發(fā)式合并，暴力往大的樹(shù)中添加葉子。

添加葉子時(shí)，需要將葉子到重心路徑上所有點(diǎn)的子樹(shù)大小+1，距離和則加上一個(gè)等差數(shù)列。

并且新的重心是可能是原來(lái)的重心或者原來(lái)重心到葉子路徑上的第一個(gè)點(diǎn)，暴力即可。

時(shí)間復(fù)雜度$O(n\log^2n)$。

?

#include<cstdio> #define N 40010 int n,m,i,x,y,ans;char op[5]; int g[N],v[N<<1],nxt[N<<1],ed,f[N],son[N][2],val[N],tag[N],sum[N],ts[N],td[N],size[N],tmp[N]; inline void swap(int&a,int&b){int c=a;a=b;b=c;} inline bool isroot(int x){return !f[x]||son[f[x]][0]!=x&&son[f[x]][1]!=x;} inline void add1(int x,int p){if(!x)return;val[x]+=p;tag[x]+=p;} inline void add2(int x,int s,int d){if(!x)return;sum[x]+=s+size[son[x][1]]*d;ts[x]+=s;td[x]+=d;} inline void pb(int x){if(tag[x]){add1(son[x][0],tag[x]);add1(son[x][1],tag[x]);tag[x]=0;}if(td[x]){add2(son[x][0],ts[x]+(size[son[x][1]]+1)*td[x],td[x]);add2(son[x][1],ts[x],td[x]);ts[x]=td[x]=0;} } inline void up(int x){size[x]=size[son[x][0]]+size[son[x][1]]+1;} inline void rotate(int x){int y=f[x],w=son[y][1]==x;son[y][w]=son[x][w^1];if(son[x][w^1])f[son[x][w^1]]=y;if(f[y]){int z=f[y];if(son[z][0]==y)son[z][0]=x;else if(son[z][1]==y)son[z][1]=x;}f[x]=f[y];f[y]=x;son[x][w^1]=y;up(y); } inline void splay(int x){int s=1,i=x,y;tmp[1]=i;while(!isroot(i))tmp[++s]=i=f[i];while(s)pb(tmp[s--]);while(!isroot(x)){y=f[x];if(!isroot(y)){if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);else rotate(y);}rotate(x);}up(x); } inline void access(int x){for(int y=0;x;y=x,x=f[x])splay(x),son[x][1]=y,up(x);} inline int root(int x){access(x);splay(x);while(son[x][0])x=son[x][0];return x;} inline void addleaf(int x,int y){f[y]=x,son[y][0]=son[y][1]=val[y]=tag[y]=sum[y]=ts[y]=td[y]=0,size[y]=1;x=root(x),access(y),splay(x),add1(x,1),add2(x,0,1);for(y=son[x][1];son[y][0];y=son[y][0]);splay(y);int vx=val[x],vy=val[y];if(vy*2>vx){val[y]=vx,val[x]-=vy;sum[x]-=sum[y]+vy,sum[y]+=sum[x]+vx-vy;access(y),splay(x),son[x][0]=y,son[x][1]=0;} } void dfs(int x,int y){addleaf(y,x);for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x); } inline void addedge(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;} inline void link(int x,int y){int X=root(x),Y=root(y);ans-=sum[X]+sum[Y];if(val[X]<val[Y])swap(x,y);dfs(y,x),addedge(x,y),addedge(y,x);ans+=sum[root(x)]; } int main(){scanf("%d%d",&n,&m);for(i=1;i<=n;i++)val[i]=size[i]=1;while(m--){scanf("%s",op);if(op[0]=='A')scanf("%d%d",&x,&y),link(x,y);if(op[0]=='Q')printf("%d\n",ans);}return 0; }

　　

總結(jié)

以上是生活随笔為你收集整理的BZOJ2888 : 资源运输的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。