题目描述：给你n个点和m个操作：
1.链接两个点。
2.查询某点所在树的重心。
3.查询所有树重心的异或和。
其实就是lct维护虚子树，链接时新重心一定在原来的两重心连线上，相当于splay查询区间第k大值（区间中点）。
代码：
#include#include #define N 100050int n,m;int fa[N],rt[N],ch[N][2],s[N],sx[N],sr;bool res[N];bool is_not_root(int x){ return (ch[fa[x]][0]==x)|(ch[fa[x]][1]==x);}void update(int x){ s[x]=s[ch[x][0]]+s[ch[x][1]]+sx[x]+1;}void reser(int x){ res[x]^=1; std::swap(ch[x][0],ch[x][1]);}void pushdown(int x){ if(res[x]) { res[x]=0; reser(ch[x][0]); reser(ch[x][1]); }}void down(int x){ if(is_not_root(x))down(fa[x]); pushdown(x);}void rotate(int x){ int y = fa[x],k = (ch[y][1]==x); if(is_not_root(y))ch[fa[y]][ch[fa[y]][1]==y]=x; fa[x]=fa[y]; ch[y][k]=ch[x][!k],fa[ch[x][!k]]=y; ch[x][!k]=y,fa[y]=x; update(y),update(x);}void splay(int x){ down(x); while(is_not_root(x)) { int y = fa[x],z=fa[y]; if(is_not_root(y)) ((ch[y][1]==x)^(ch[z][1]==y))?rotate(x):rotate(y); rotate(x); }}void access(int x){ int y = 0; while(x) { splay(x); sx[x]+=s[ch[x][1]]; sx[x]-=s[y]; ch[x][1]=y; update(x); y=x,x=fa[x]; }}void mtr(int x){ access(x); splay(x); reser(x);}void split(int x,int y){ mtr(x); access(y); splay(y);}void link(int x,int y){ split(x,y); fa[x]=y; sx[y]+=s[x]; update(y);}int findrt(int x){ if(rt[x]==x)return x; return rt[x]=findrt(rt[x]);}int getfa(int x){ int goal = s[x]>>1,tip = (s[x]&1); int ls = 0,rs = 0,ret = 0x7fffffff,vl,vr; while(x) { pushdown(x); vl = s[ch[x][0]]+ls; vr = s[ch[x][1]]+rs; if(vl<=goal&&vr<=goal) { if(tip){ret=x;break;} else if(ret>x)ret=x; } if(vl>vr) { rs += s[ch[x][1]]+sx[x]+1; x = ch[x][0]; }else { ls += s[ch[x][0]]+sx[x]+1; x = ch[x][1]; } } splay(ret); return ret;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { s[i]=1; sr^=i; rt[i]=i; } int u,v; char sc[10]; for(int i=1;i<=m;i++) { scanf("%s",sc); if(sc[0]=='X') { printf("%d\n",sr); }else if(sc[0]=='Q') { scanf("%d",&u); printf("%d\n",findrt(u)); }else { scanf("%d%d",&u,&v); link(u,v); u=findrt(u),v=findrt(v); split(u,v);//v=rt int r = getfa(v); sr = sr^u^v^r; rt[u] = rt[v] = rt[r] = r; } } return 0;}