题目描述
在X星球上有N个国家，每个国家占据着X星球的一座城市。由于国家之间是敌对关系，所以不同国家的两个城市是不会有公路相连的。
X星球上战乱频发，如果A国打败了B国，那么B国将永远从这个星球消失，而B国的国土也将归A国管辖。A国国王为了加强统治，会在A国和B国之间修建一条公路，即选择原A国的某个城市和B国某个城市，修建一条连接这两座城市的公路。
同样为了便于统治自己的国家，国家的首都会选在某个使得其他城市到它距离之和最小的城市，这里的距离是指需要经过公路的条数，如果有多个这样的城市，编号最小的将成为首都。
现在告诉你发生在X星球的战事，需要你处理一些关于国家首都的信息，具体地，有如下3种信息需要处理：
1、A x y：表示某两个国家发生战乱，战胜国选择了x城市和y城市，在它们之间修建公路（保证其中城市一个在战胜国另一个在战败国）。
2、Q x：询问当前编号为x的城市所在国家的首都。
3、Xor：询问当前所有国家首都编号的异或和。
输入
第一行是整数N，M，表示城市数和需要处理的信息数。
接下来每行是一个信息，格式如题目描述（A、Q、Xor中的某一种）。
输出
输出包含若干行，为处理Q和Xor信息的结果。
样例输入
10 10
Xor
Q 1
A 10 1
A 1 4
Q 4
Q 10
A 7 6
Xor
Q 7
Xor
样例输出
11
1
1
1
2
6
2
题解
LCT维护子树信息
看了好几个小时的题解还是半懂不懂orz
先考虑连接两棵树
有两个性质
1.重心必在点数多的子树内
2.点数多的子树上重心移动的距离不超过点数少的子树的点数
然后就是连上之后，把这条路径拉出来，dfs一遍，枚举选哪一个点，然后判一下最优就好了
// luogu-judger-enable-o2
//minamoto
#include<iostream>
#include<cstdio>
#include<algorithm>
using std::swap;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
char obuf[<<],*o=obuf;
inline void print(int x){
if(x>) print(x/);
*o++=x%+;
}
const int N=;
int fa[N],st[N],sum[N],si[N],rev[N],ch[N][],top,s;
inline bool isroot(int x){return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;}
inline void pushup(int x){sum[x]=sum[ch[x][]]+sum[ch[x][]]+si[x]+;}
inline void pushdown(int x){
if(rev[x]){
swap(ch[x][],ch[x][]);
rev[ch[x][]]^=,rev[ch[x][]]^=;
rev[x]=;
}
}
void rotate(int x){
int y=fa[x],z=fa[y],d=ch[y][]==x;
if(!isroot(y)) ch[z][ch[z][]==y]=x;
fa[x]=z,fa[y]=x,fa[ch[x][d^]]=y,ch[y][d]=ch[x][d^],ch[x][d^]=y,pushup(y);
}
void down(int x){
if(!isroot(x)) down(fa[x]);
pushdown(x);
}
void splay(int x){
down(x);
for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){
if(!isroot(y))
((ch[y][]==x)^(ch[z][]==y))?rotate(x):rotate(y);
rotate(x);
}
pushup(x);
}
void access(int x){
for(int y=;x;x=fa[y=x])
splay(x),si[x]+=sum[ch[x][]],si[x]-=sum[ch[x][]=y],pushup(x);
}
void makeroot(int x){
access(x),splay(x),rev[x]^=;
}
int findroot(int x){
access(x),splay(x),pushdown(x);
while(ch[x][]) pushdown(x=ch[x][]);
return x;
}
void split(int x,int y){
makeroot(x),access(y),splay(y);
}
void link(int x,int y){
split(x,y),fa[x]=y,si[y]+=sum[x],pushup(y);
}
void dfs(int x){
pushdown(x);
if(ch[x][]) dfs(ch[x][]);
if(top>s) return;
st[++top]=x;
if(top>s) return;
if(ch[x][]) dfs(ch[x][]);
}
int main(){
//freopen("testdata.in","r",stdin);
int n=read(),m=read(),res=;
for(int i=;i<=n;++i) sum[i]=,res^=i;
while(m--){
char c;
while((c=getc())!='Q'&&c!='A'&&c!='X');
switch(c){
case 'A':{
int x=read(),y=read();
int tx=findroot(x),ty=findroot(y),ts;
res^=tx^ty;
splay(tx),splay(ty);
if(sum[tx]>sum[ty]||(sum[tx]==sum[ty]&&x<y)) swap(x,y),swap(tx,ty);
s=sum[tx],ts=sum[tx]+sum[ty],link(x,y),access(x),splay(ty);
top=,dfs(ty);int r=ty;
for(int i=;i<=top;++i){
splay(st[i]);int t=si[st[i]]++sum[ch[st[i]][]];
if(ts-t<t||(ts-t==t&&st[i]<=r)) r=st[i];
else break;
/*枚举原重心到连接点之间的路径
t表示枚举到某一点时另一棵子树的大小
如果这棵子树大于另一边或那啥，更新答案
否则之前的答案最优，直接退出*/
}
makeroot(r),res^=r;
break;
}
case 'Q':{
int x=read();
print(findroot(x)),*o++='\n';
break;
}
case 'X':{
print(res),*o++='\n';
break;
}
}
}
fwrite(obuf,o-obuf,,stdout);
return ;
}