没什么可说的，就是一个可持久化线段树维护一个数组fa以及deep按秩合并好了
注意一下强制在线
蒟蒻的我搞了好长时间QAQ
贴代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
struct trnt{
int ls;
int rs;
int fa;
int dp;
}tr[];
int root[];
int siz;
int n,m;
int lastans;
void Tr_build(int l,int r,int &spc)
{
if(!spc)
spc=++siz;
if(l==r)
{
tr[spc].fa=l;
return ;
}
int mid=(l+r)/;
Tr_build(l,mid,tr[spc].ls);
Tr_build(mid+,r,tr[spc].rs);
return ;
}
int ask(int l,int r,int pos,int spc)
{
if(l==r)
return spc;
int mid=(l+r)/;
if(pos<=mid)
return ask(l,mid,pos,tr[spc].ls);
return ask(mid+,r,pos,tr[spc].rs);
}
int finf(int rt,int x)
{
int ff=ask(,n,x,rt);
if(tr[ff].fa==x)
return ff;
return finf(rt,tr[ff].fa);
}
void unin(int l,int r,int &spc,int last,int pos,int ff)
{
spc=++siz;
if(l==r)
{
tr[spc].fa=ff;
tr[spc].dp=tr[last].dp;
return ;
}
tr[spc].ls=tr[last].ls;
tr[spc].rs=tr[last].rs;
int mid=(l+r)/;
if(pos<=mid)
unin(l,mid,tr[spc].ls,tr[last].ls,pos,ff);
else
unin(mid+,r,tr[spc].rs,tr[last].rs,pos,ff);
return ;
}
void grow(int l,int r,int pos,int spc)
{
if(l==r)
{
tr[spc].dp++;
return ;
}
int mid=(l+r)/;
if(pos<=mid)
grow(l,mid,pos,tr[spc].ls);
else
grow(mid+,r,pos,tr[spc].rs);
return ;
}
int main()
{
scanf("%d%d",&n,&m);
Tr_build(,n,root[]);
for(int i=;i<=m;i++)
{
root[i]=root[i-];
int cmd;
scanf("%d",&cmd);
if(cmd==)
{
int x,y;
scanf("%d%d",&x,&y);
x=x^lastans;
y=y^lastans;
x=finf(root[i],x);
y=finf(root[i],y);
if(tr[x].fa==tr[y].fa)
continue;
if(tr[x].dp>tr[y].dp)
std::swap(x,y);
unin(,n,root[i],root[i-],tr[x].fa,tr[y].fa);
if(tr[x].dp==tr[y].dp)
grow(,n,tr[y].fa,root[i]);
}else if(cmd==)
{
int x;
scanf("%d",&x);
x=x^lastans;
root[i]=root[x];
}else{
int x,y;
scanf("%d%d",&x,&y);
x=x^lastans;
y=y^lastans;
x=finf(root[i],x);
y=finf(root[i],y);
if(tr[x].fa==tr[y].fa)
lastans=;
else
lastans=;
printf("%d\n",lastans);
}
}
return ;
}