题目描述
在X星球上有N个国家，每个国家占据着X星球的一座城市。由于国家之间是敌对关系，所以不同国家的两个城市是不会有公路相连的。
X星球上战乱频发，如果A国打败了B国，那么B国将永远从这个星球消失，而B国的国土也将归A国管辖。A国国王为了加强统治，会在A国和B国之间修建一条公路，即选择原A国的某个城市和B国某个城市，修建一条连接这两座城市的公路。
同样为了便于统治自己的国家，国家的首都会选在某个使得其他城市到它距离之和最小的城市，这里的距离是指需要经过公路的条数，如果有多个这样的城市，编号最小的将成为首都。
现在告诉你发生在X星球的战事，需要你处理一些关于国家首都的信息，具体地，有如下3种信息需要处理：
A x y：表示某两个国家发生战乱，战胜国选择了x城市和y城市，在它们之间修建公路（保证其中城市一个在战胜国另一个在战败国）。Q x：询问当前编号为x的城市所在国家的首都。Xor：询问当前所有国家首都编号的异或和。
题解
有link操作还询问重心，是让我们在维护LCT的时候维护一下重心。
这道题用到了LCT的很多性质。
比如说我们link了两棵树，那么我们拿出两棵树的重心，那么重心一定在这两条链的路径上，我们把这条链split出来。
根据splay的性质，这条链构成的splay的高度是期望log的。
然后我们就可以从根开始搜索了。
既然是log的，那么我们就可以用类似树上二分的方法找了。
连通性这种东西用并查集维护就可以了。
LCT维护子树信息时link一定要splay(y)!!!!!
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100009
using namespace std;
char sh[];
int f[N],ch[N][],s[N],si[N],fa[N],n,m,st[N],xoR;
bool rev[N];
inline int rd(){
int x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
inline int find(int x){return f[x]=f[x]==x?x:find(f[x]);}
inline bool isroot(int x){return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;}
inline bool ge(int x){return ch[fa[x]][]==x;}
inline void pushup(int x){s[x]=s[ch[x][]]+s[ch[x][]]+si[x]+;}
inline void pushdown(int x){
if(rev[x]){
rev[ch[x][]]^=;rev[ch[x][]]^=;rev[x]^=;
swap(ch[x][],ch[x][]);
}
}
inline void rotate(int x){
int y=fa[x],o=ge(x);
if(isroot(x))return;
ch[y][o]=ch[x][o^];fa[ch[y][o]]=y;
if(!isroot(y))ch[fa[y]][ge(y)]=x;fa[x]=fa[y];
fa[y]=x;ch[x][o^]=y;
pushup(y);pushup(x);
}
inline void push(int x){
if(!isroot(x))push(fa[x]);
pushdown(x);
}
inline void splay(int x){
push(x);
while(!isroot(x)){
int y=fa[x];
if(isroot(y))rotate(x);
else rotate(ge(x)==ge(y)?y:x),rotate(x);
}
pushup(x);
}
inline void access(int x){
for(int y=;x;y=x,x=fa[x]){
splay(x);
si[x]-=s[y];si[x]+=s[ch[x][]];ch[x][]=y;
pushup(x);
}
}
inline void makeroot(int x){access(x);splay(x);rev[x]^=;}
inline void split(int x,int y){makeroot(x);access(y);splay(y);}
inline void link(int x,int y){split(x,y);fa[x]=y;si[y]+=s[x];pushup(y);}
inline int search(int x){
int suml=,sumr=,rs,ls,sum=s[x]>>,o=s[x]&,now=2e9,xx,yy;
while(x){
pushdown(x);
xx=suml+s[ls=ch[x][]];yy=sumr+s[rs=ch[x][]];
if(xx<=sum&&yy<=sum){
if(o){now=x;break;}
else if(x<now)now=x;
}
if(xx<yy)suml+=s[ls]+si[x]+,x=rs;
else sumr+=s[rs]+si[x]+,x=ls;
}
return now;
}
int main(){
n=rd();m=rd();int x,y;
for(int i=;i<=n;++i)s[i]=,f[i]=i,xoR^=i;
for(int i=;i<=m;++i){
scanf("%s",sh);
if(sh[]=='A'){
x=rd();y=rd();//if(find(x)==find(y))continue;
link(x,y);x=find(x);y=find(y);
split(x,y);int z=search(y);
xoR=xoR^x^y^z;
f[x]=f[y]=f[z]=z;
}
else if(sh[]=='Q'){x=rd();printf("%d\n",find(x));}
else printf("%d\n",xoR);
}
return ;
}