即动态维护树的重心。考虑合并后的新重心一定在两棵树的重心的连线上。于是对每个点维护其子树大小，合并时在这条链的splay上二分即可。至于如何维护子树大小，见https://blog.csdn.net/neither_nor/article/details/52979425。明明都看那么多题解说要注意pushdown，结果还是因为这个调了一年，心态爆炸。（下面代码复杂度可能是假的，因为dfs完没有splay叶子，反正也没人卡我就不管了）
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 100010 #define M 200010 #define lson tree[k].ch[0] #define rson tree[k].ch[1] #define lself tree[tree[k].fa].ch[0] #define rself tree[tree[k].fa].ch[1] char getc(){char c=getchar();while (c<'A'||c>'Z') c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,ans; struct data{int ch[2],fa,rev,size_f,size; }tree[N]; void up(int k){tree[k].size=tree[lson].size+tree[rson].size+tree[k].size_f+1;} void rev(int k){if (k) swap(lson,rson),tree[k].rev^=1;} void down(int k){if (tree[k].rev) rev(lson),rev(rson),tree[k].rev=0;} bool isroot(int k){return lself!=k&&rself!=k;} int whichson(int k){return rself==k;} void push(int k){if (!isroot(k)) push(tree[k].fa);down(k);} void move(int k) { int fa=tree[k].fa,gf=tree[fa].fa,p=whichson(k); if (!isroot(fa)) tree[gf].ch[whichson(fa)]=k;tree[k].fa=gf; tree[tree[k].ch[!p]].fa=fa,tree[fa].ch[p]=tree[k].ch[!p]; tree[k].ch[!p]=fa,tree[fa].fa=k; up(fa),up(k); } void splay(int k) { push(k); while (!isroot(k)) { int fa=tree[k].fa; if (!isroot(fa)) if (whichson(k)^whichson(fa)) move(k); else move(fa); move(k); } } void access(int k) { for (int t=0;k;t=k,k=tree[k].fa) { splay(k); tree[k].size_f+=tree[rson].size; rson=t; tree[k].size_f-=tree[rson].size; up(k); } } void makeroot(int k){access(k),splay(k),rev(k);} int findroot(int k){access(k),splay(k);for (;lson;k=lson) down(k);splay(k);return k;} int dfs(int k,int s,int r) { if (!k) return n+1; down(k); if (s-(tree[k].size-tree[lson].size+r)<=(s>>1)) { int x=dfs(rson,s,r); if (x<=n) return x;else return k; } else return dfs(lson,s,r+tree[k].size-tree[lson].size); } int find(int k){down(k);if (rson) return find(rson);else return k;} void link(int x,int y) { int p=findroot(x),q=findroot(y);ans^=p,ans^=q; makeroot(y),access(x),splay(x),tree[y].fa=x; tree[x].size_f+=tree[y].size,up(x); makeroot(p),access(q),splay(q);int s=tree[q].size; p=dfs(q,s,0),splay(p); if (tree[p].size-tree[tree[p].ch[0]].size<=(s>>1)) splay(q=find(tree[p].ch[0])),p=min(p,q); makeroot(p);ans^=p; } int main() { #ifndef ONLINE_JUDGE freopen("bzoj3510.in","r",stdin); freopen("bzoj3510.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(); for (int i=1;i<=n;i++) ans^=i,tree[i].size=1; while (m--) { char c=getc(); if (c=='X') printf("%d ",ans); if (c=='A') link(read(),read()); if (c=='Q') printf("%d ",findroot(read())); } return 0; }