到所有点距离和最小的点就是重心
因为只有link操作，我们可以考虑启发式合并，这样最多会有n log n次“插入一个叶子节点”操作
一棵树插入一个叶子节点之后，重心要么不变，要么向叶子的方向移动一条边，移动的条件是叶子所在的子树大小*2大于这棵树的大小（或者相等取编号小的）
用LCT维护子树大小即可
有关LCT维护子树信息的讲解可以看这里
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<vector> #include<map> #include<set> #include<bitset> #include<queue> #include<stack> using namespace std; #define MAXN 100010 #define MAXM 1010 #define INF 1000000000 #define MOD 1000000007 #define eps 1e-8 #define ll long long struct vec{ int to; int fro; }; vec mp[MAXN*2]; int tai[MAXN],cnt; int fa[MAXN],son[MAXN][2],siz[MAXN],Siz[MAXN]; bool rev[MAXN]; int st[MAXN],tp; int rt[MAXN]; int F[MAXN],SIZ[MAXN]; int xs; int n,m; void pt(){ int i; for(i=1;i<=n;i++){ cerr<<son[i][0]<<' '<<son[i][1]<<' '<<fa[i]<<endl; } cerr<<"-------"<<endl; } inline void be(int x,int y){ mp[++cnt].to=y; mp[cnt].fro=tai[x]; tai[x]=cnt; } inline void bde(int x,int y){ be(x,y); be(y,x); } int FA(int x){ return F[x]==x?x:F[x]=FA(F[x]); } inline bool ir(int x){ return son[fa[x]][0]!=x&&son[fa[x]][1]!=x; } inline void cot(int x,int y,bool z){ if(x){ fa[x]=y; } if(y){ son[y][z]=x; } } inline void torev(int x){ if(!x){ return ; } swap(son[x][0],son[x][1]); rev[x]^=1; } inline void ud(int x){ siz[x]=siz[son[x][0]]+siz[son[x][1]]+1+Siz[x]; } inline void pd(int x){ if(rev[x]){ torev(son[x][0]); torev(son[x][1]); rev[x]=0; } } inline void rot(int x,bool z){ int xx=fa[x],xxx=fa[xx]; cot(son[x][z],xx,z^1); if(ir(xx)){ fa[x]=xxx; }else{ cot(x,xxx,son[xxx][1]==xx); } cot(xx,x,z); ud(xx); } inline void apd(int x){ int i; st[++tp]=x; for(i=x;!ir(i);i=fa[i]){ st[++tp]=fa[i]; } for(;tp;tp--){ pd(st[tp]); } } void splay(int x){ apd(x); while(!ir(x)){ int xx=fa[x],xxx=fa[xx]; if(ir(xx)){ rot(x,son[xx][0]==x); }else{ bool z=son[xxx][0]==xx; if(son[xx][z]==x){ rot(x,z^1); rot(x,z); }else{ rot(xx,z); rot(x,z); } } } ud(x); } inline void acs(int x){ int t=0; while(x){ splay(x); Siz[x]+=siz[son[x][1]]-siz[t]; son[x][1]=t; ud(x); t=x; x=fa[x]; } } inline void reboot(int x){ acs(x); splay(x); torev(x); } inline void link(int x,int y){ reboot(x); reboot(y); fa[x]=y; Siz[y]+=siz[x]; ud(y); reboot(rt[FA(y)]); acs(x); splay(rt[FA(y)]); int S=siz[rt[FA(y)]]; int t=son[rt[FA(y)]][1]; pd(t); while(son[t][0]){ t=son[t][0]; pd(t); } acs(t); if((Siz[t]+1)*2>S||(Siz[t]+1)*2==S&&t<rt[FA(y)]){ xs^=rt[FA(y)]; xs^=t; rt[FA(y)]=t; } } void dfs(int x,int f){ int i,y; son[x][0]=son[x][1]=fa[x]=rev[x]=0; Siz[x]=0; siz[x]=1; link(x,f); for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(y!=f){ dfs(y,x); } } } int main(){ int i,x,y; char o[5]; scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ F[i]=i; rt[i]=i; siz[i]=SIZ[i]=1; xs^=i; } while(m--){ scanf("%s",o); if(o[0]=='A'){ scanf("%d%d",&x,&y); if(SIZ[FA(x)]>SIZ[FA(y)]){ swap(x,y); } SIZ[FA(y)]+=SIZ[FA(x)]; xs^=rt[FA(x)]; F[FA(x)]=FA(y); dfs(x,y); bde(x,y); } if(o[0]=='Q'){ scanf("%d",&x); printf("%d\n",rt[FA(x)]); } if(o[0]=='X'){ printf("%d\n",xs); } } return 0; } /* 9 9 A 1 2 A 3 4 A 5 4 A 4 6 A 1 7 A 1 8 A 1 4 A 3 9 Q 1 */