题目大意：给你一颗树，边是一条一条连上去的
在连接过程中会存在询问，询问当前节点所在联通块(其实是一颗树)的重心是哪个节点
以及森林中所有树的重心的异或和
在做这道题之前，要先了解树的重心的一个性质：
两棵树合并时，新树的重心在合并后，原来两颗树的重心的两个节点构成的那条链上
了解了这条性质，思路就不难想了
当连接两个节点时，先寻找它们所在原树的重心，然后连接这两个节点，在取出两个原树重心那两个节点构成的那条链
每次寻找重心，连接节点，取出重心形成了链，复杂度约为
如果我们暴力跑这条链，最差的情况是每次合并时，两颗树都是等长的链，然后像线段树那样从下往上合并，合并次数最多是次，注意符合条件的重心最多只有2个，且子树的大小符合单调性，当越过所有重心时，及时跳出循环防止卡常
总复杂度
然而我还是喜闻乐见得被卡常了
#include <cstdio>
#include <cstring>
#include <algorithm>
#define il inline
#define N 200100
using namespace std; int n,m,tp,num,xsum;
int stk[N],que[N]; struct LinkCutTree{
#define ls ch[x][0]
#define rs ch[x][1]
int fa[N],ch[N][],sz[N],sum[N],rv[N];
il int idf(int x){return ch[fa[x]][]==x?:;}
il void rev(int x){swap(ls,rs),rv[x]^=;}
il int isroot(int x){return (ch[fa[x]][]!=x&&ch[fa[x]][]!=x)?:;}
il void pushup(int x){sum[x]=sum[ls]+sum[rs]+sz[x]+;}
il void pushdown(int x)
{
if(rv[x]){
if(ls) rev(ls);
if(rs) rev(rs);
rv[x]^=;
}
}
il void rot(int x)
{
int y=fa[x],ff=fa[y],px=idf(x),py=idf(y);
if(!isroot(y)) ch[ff][py]=x;fa[x]=ff;
ch[y][px]=ch[x][px^],fa[ch[x][px^]]=y;
ch[x][px^]=y,fa[y]=x;
pushup(y),pushup(x);
}
void splay(int x)
{
int y=x;stk[++tp]=x;
while(!isroot(y)){stk[++tp]=fa[y],y=fa[y];}
while(tp){pushdown(stk[tp--]);}
while(!isroot(x))
{
y=fa[x];
if(isroot(y)) rot(x);
else if(idf(y)==idf(x)) rot(y),rot(x);
else rot(x),rot(x);
}
}
void access(int x){
for(int y=;x;y=x,x=fa[x])
splay(x),sz[x]-=sum[y],sz[x]+=sum[ch[x][]],ch[x][]=y,pushup(x);}
il void mkroot(int x){access(x),splay(x),rev(x);}
il void split(int x,int y){mkroot(y),access(x),splay(x);}
il int findrt(int x){
access(x),splay(x);
while(){
pushdown(x);
if(!ch[x][])break;
x=ch[x][];}
splay(x);return x;
}
void mid_dfs(int x)
{
pushdown(x);
if(ls) mid_dfs(ls);
que[++num]=x;
if(rs) mid_dfs(rs);
}
il void link(int x,int y)
{
int gx=findrt(x),gy=findrt(y);
xsum=xsum^gx^gy;
if(sum[gx]<sum[gy]) swap(x,y),swap(gx,gy);
split(x,y),fa[y]=x,sz[x]+=sum[y],pushup(x);
num=,split(gy,gx),mid_dfs(gy);
int ma=sum[gy]/,ans=0x3f3f3f3f;
for(int i=;i<=num;i++){
splay(que[i]);
if(sum[ch[que[i]][]]<=ma&&sum[ch[que[i]][]]<=ma&&que[i]<ans)
ans=que[i];
if(sum[ch[que[i]][]]>ma) break;}
mkroot(ans);
xsum^=ans;
}
#undef ls
#undef rs
}lct;
int gint()
{
int rett=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){rett=(rett<<)+(rett<<)+c-'';c=getchar();}
return rett*fh;
}
void gchar(char str[])
{
int p=;char c=getchar();
while(!((c>='A'&&c<='Z')||(c>='a'&&c<='z'))){c=getchar();}
while((c>='A'&&c<='Z')||(c>='a'&&c<='z')){str[p++]=c;c=getchar();}
str[p]='\0';
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) xsum^=i;
char q[];int x,y;
for(int i=;i<=m;i++)
{
gchar(q);
if(q[]=='A'){
x=gint(),y=gint();
lct.link(x,y);
}else if(q[]=='Q'){
x=gint();
printf("%d\n",lct.findrt(x));
}else printf("%d\n",xsum);
}
return ;
}