按秩合并并查集求助

#include<bits/stdc++.h>
int read()
{
	char ch=getchar();
	int x=0;
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
		x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
	return x;
}
template <class type>
type max(type a,type b){return a>b?a:b;}
const int N=5e5+5;
int n,m,f[N],dep[N],depth[N],dis[N],lasans,rid;
int find(int x)
{
	if(f[x]==x)
		return x;
	int F=find(f[x]);
	dep[x]=dep[f[x]]+1;
	return F;
}
void merge(int u,int v,int w)
{
	int fu=find(u),fv=find(v);
	if(fu==fv)
		return;
	if(depth[u]<depth[v])
	{
		std::swap(fu,fv);
		std::swap(u,v);
	}
	f[fv]=fu;
	depth[fu]=max(depth[fu],depth[fv]+1);
	dis[fv]=w;
}
int query(int u,int v)
{
	int fu=find(u),fv=find(v);
	if(fu!=fv)
		return 0;
	int res=0;
	while(u!=v)
	{
		if(dep[u]>dep[v])
			res=max(res,dis[u]),u=f[u];
		else
			res=max(res,dis[v]),v=f[v];
	}
	return res;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		f[i]=i,dep[i]=1,depth[i]=1;
	for(int i=1,opt,u,v;i<=m;++i)
	{
		opt=read(),u=read(),v=read();
		u^=lasans;
		v^=lasans;
		if(!opt)
		{
			++rid;
			merge(u,v,rid);
		}
		else
		{
			lasans=query(u,v);
			printf("%d\n",lasans);
		}
	}
}