题目Link

代码：

#include <cstdio>
const int maxn = 3e5+5;
inline int max(int a,int b){return a>b?a:b;}
inline void swap(int &a,int &b){a ^= b,b ^= a,a ^= b;}
int Type,lastans,n,m;
int prt[maxn],L[maxn],R[maxn];
inline int getfa(int x){return x == prt[x] ? x : prt[x] = getfa(prt[x]);}
int ch[maxn][2],fa[maxn],siz[maxn],rev[maxn];
inline int identify(int x){return ch[fa[x]][1] == x;}
inline void pushup(int x){siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;}
inline int nroot(int x){return ch[fa[x]][0] == x || ch[fa[x]][1] == x;}
inline void grev(int x){rev[x] ^= 1,swap(ch[x][0],ch[x][1]);}
inline void pushdown(int x){if(rev[x])rev[x] = 0,grev(ch[x][0]),grev(ch[x][1]);}
inline void connect(int x,int F,int sid){ch[F][sid] = x,fa[x] = F;}
inline void rotate(int x){
	int y = fa[x],z = fa[y],xy = identify(x),yz = identify(y),nry = nroot(y);
	connect(ch[x][xy^1],y,xy),connect(y,x,xy^1),fa[x] = z;
	if(nry)ch[z][yz] = x;
	pushup(y),pushup(x);
}
inline void pushtag(int x){
	if(nroot(x))pushtag(fa[x]);
	pushdown(x);
}
inline void Splay(int x){
	pushdown(x);
	while(nroot(x)){
		int y = fa[x];
		if(nroot(y))identify(x)^identify(y)?rotate(x):rotate(y);
		rotate(x);
	}
}
inline void access(int x){for(int y=0;x;x=fa[y=x])Splay(x),ch[x][1] = y,pushup(x);}
inline void evert(int x){access(x),Splay(x),grev(x);}
inline void split(int x,int y){evert(x),access(y),Splay(y);}
inline void link(int x,int y){evert(x),fa[x] = y;}
inline int Query(int x,int y){split(x,y);return siz[y]-1;}
int main(){
	scanf("%d",&Type);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)prt[i] = L[i] = R[i] = i;
	for(int i=1,ty,x,y;i<=m;++i){
		scanf("%d",&ty);
		if(ty == 1){
			scanf("%d %d",&x,&y),((Type==1)?(x^=lastans,y^lastans):0);
			int fx = getfa(x),fy = getfa(y),l,r,temp,dis=-1;
			int a = L[fx],b = L[fy],c = R[fx],d = R[fy];
			link(x,y);
			if((temp=Query(a,b)) > dis)dis = temp,l = a,r = b;
			if((temp=Query(a,d)) > dis)dis = temp,l = a,r = d;
			if((temp=Query(a,c)) > dis)dis = temp,l = a,r = c;
			if((temp=Query(b,c)) > dis)dis = temp,l = b,r = c;
			if((temp=Query(b,d)) > dis)dis = temp,l = b,r = d;
			if((temp=Query(c,d)) > dis)dis = temp,l = c,r = d;
			printf("link:%d %d %d\n",dis,l,r);
			prt[fx] = fy,L[fy] = l,R[fy] = r;
		}
		if(ty == 2){
			scanf("%d",&x),((Type==1)?(x^=lastans):0),lastans = i;
			int fx = getfa(x);
			printf("Q : %d %d %d\n",L[fx],R[fx],fx);
			printf("%d\n",max(Query(L[fx],x),Query(R[fx],x)));
		}
//		puts(""); 
//		for(int j=1;j<=n;++j)printf("%d %d %d\n",getfa(j),L[j],R[j]);
//		puts(""); 
//		puts(""); 
//		for(int j=1;j<=n;++j)printf("%d %d %d\n",fa[j],ch[j][0],ch[j][1]);
//		puts(""); 
	}
	return 0;
}

目前样例输出

0
1
0
2
3
2

马蜂可能略显毒瘤