解析

動態(tài)維護樹的重心
關鍵性質：兩棵樹合并時，新的重心一定在兩個原重心之間的路徑上
把兩個重心之間的路徑提出來，利用splay本身的二叉結構二分即可
注意虛子樹信息的處理
不要忘記pushdown

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=3e5+100; const int mod=1e9+7; const double eps=1e-9; inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m; int flag; int tr[N][2],f[N],rev[N]; int siz[N],siz0[N]; #define ls(u) tr[u][0] #define rs(u) tr[u][1] inline bool isroot(int x){return ls(f[x])!=x&&rs(f[x])!=x; } inline bool which(int x){return rs(f[x])==x; } inline void pushup(int x){if(x) siz[x]=siz[ls(x)]+siz[rs(x)]+siz0[x]+1;return; } inline void Rev(int x){if(x){rev[x]^=1;swap(tr[x][0],tr[x][1]);}return; } inline void pushdown(int x){if(rev[x]){rev[x]=0;Rev(tr[x][0]);Rev(tr[x][1]);}return; } void print(int x){if(!x) return;pushdown(x);printf("x=%d ls=%d rs=%d fa=%d siz=%d siz0=%d\n",x,ls(x),rs(x),f[x],siz[x],siz0[x]);print(ls(x));print(rs(x)); } void Debug(){//printf("debug:\n");for(int i=1;i<=n;i++) if(isroot(i)) print(i);putchar('\n'); } inline void rotate(int x){int fa=f[x],gfa=f[fa];int d=which(x),son=tr[x][d^1];f[x]=gfa;if(!isroot(fa)) tr[gfa][which(fa)]=x;f[fa]=x;tr[x][d^1]=fa;if(son){f[son]=fa;}tr[fa][d]=son;pushup(fa);pushup(x);return; } int zhan[N]; inline void splay(int x){int y=x,top(0);zhan[++top]=y;while(!isroot(y)) zhan[++top]=y=f[y];while(top){//printf(" pushdown:%d\n",y);pushdown(zhan[top--]);}for(int fa;fa=f[x],!isroot(x);rotate(x)){if(!isroot(fa)) which(x)==which(fa)?rotate(fa):rotate(x);}return; } inline void access(int x){for(int y=0;x;y=x,x=f[x]){splay(x);siz0[x]+=siz[rs(x)];siz0[x]-=siz[y];rs(x)=y;pushup(x);if(y) f[y]=x;}return; } inline void makeroot(int x){//if(flag) printf("makeroot:%d\n\n",x);access(x);//if(flag) printf("access:\n"),Debug();splay(x);Rev(x);return; } inline void link(int x,int y){makeroot(x);access(y);splay(y);siz0[y]+=siz[x];f[x]=y;pushup(y);return; } inline void split(int x,int y){//if(flag) printf("split:(%d %d)\n",x,y);makeroot(x);//printf("makeroot:\n");Debug();access(y);//printf("access:\n");Debug();splay(y);//printf("splay:\n");Debug();return; }int fa[N]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]); }int solve(int x,int y){//printf("pre:\n");Debug();split(y,x);//Debug();int l(0),r(0),lsum(0),rsum(0),ans(0),tot=siz[x];while(x){pushdown(x);l=ls(x);r=rs(x);int lsiz=lsum+siz[l],rsiz=rsum+siz[r];//printf("x=%d l=%d r=%d tot=%d lsiz=%d rsiz=%d\n",x,l,r,tot,lsiz,rsiz);if(lsiz<=tot/2&&rsiz<=tot/2){ if(!ans||x<ans) ans=x;if(tot&1) break;}if(lsiz>rsiz){rsum+=siz[r]+siz0[x]+1;x=l;}else{lsum+=siz[l]+siz0[x]+1;x=r;}//printf(" lsum=%d rsum=%d\n",lsum,rsum);}splay(ans);return ans; }int now; char s[10]; int main() { #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifn=read();m=read();for(int i=1;i<=n;i++){siz[i]=1;now^=i;fa[i]=i;}for(int i=1;i<=m;i++){scanf(" %s",s+1);//if(i==5) flag=1;if(s[1]=='X') printf("%d\n",now);else if(s[1]=='Q') printf("%d\n",find((int)read()));else{int x=read(),y=read();link(x,y);if(flag) printf("link:\n"),Debug();x=find(x);y=find(y);int z=solve(x,y);now^=x^y;now^=z;fa[z]=fa[x]=fa[y]=z;//printf("i=%d x=%d y=%d z=%d\n\n",i,x,y,z);}//if(flag) printf("finish:\n"),Debug();}return 0; }

總結

以上是生活随笔為你收集整理的P4299 首都（LCT、重心）的全部內容，希望文章能夠幫你解決所遇到的問題。

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