题目描述
在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[10]; int f[N],ch[N][2],s[N],si[N],fa[N],n,m,st[N],xoR; bool rev[N]; inline int rd(){ int x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);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]][0]!=x&&ch[fa[x]][1]!=x;} inline bool ge(int x){return ch[fa[x]][1]==x;} inline void pushup(int x){s[x]=s[ch[x][0]]+s[ch[x][1]]+si[x]+1;} inline void pushdown(int x){ if(rev[x]){ rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;rev[x]^=1; swap(ch[x][0],ch[x][1]); } } inline void rotate(int x){ int y=fa[x],o=ge(x); if(isroot(x))return; ch[y][o]=ch[x][o^1];fa[ch[y][o]]=y; if(!isroot(y))ch[fa[y]][ge(y)]=x;fa[x]=fa[y]; fa[y]=x;ch[x][o^1]=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=0;x;y=x,x=fa[x]){ splay(x); si[x]-=s[y];si[x]+=s[ch[x][1]];ch[x][1]=y; pushup(x); } } inline void makeroot(int x){access(x);splay(x);rev[x]^=1;} 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=0,sumr=0,rs,ls,sum=s[x]>>1,o=s[x]&1,now=2e9,xx,yy; while(x){ pushdown(x); xx=suml+s[ls=ch[x][0]];yy=sumr+s[rs=ch[x][1]]; if(xx<=sum&&yy<=sum){ if(o){now=x;break;} else if(x<now)now=x; } if(xx<yy)suml+=s[ls]+si[x]+1,x=rs; else sumr+=s[rs]+si[x]+1,x=ls; } return now; } int main(){ n=rd();m=rd();int x,y; for(int i=1;i<=n;++i)s[i]=1,f[i]=i,xoR^=i; for(int i=1;i<=m;++i){ scanf("%s",sh); if(sh[0]=='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[0]=='Q'){x=rd();printf("%d ",find(x));} else printf("%d ",xoR); } return 0; }