orz TPLY 巨佬，题解讲的挺好的。
这里重点梳理一下思路，做一个小小的补充吧。
写可持久化线段树，叶子节点维护每个位置的fa，利用每次只更新一个节点的特性，每次插入\(logN\)个节点，这一部分思路还是很轻松。关于此部分的其它问题可以参考下我的可持久化线段树总结
一开始，写惯了常规并查集、用惯了路径压缩的我，以为在这一题里也要这么搞。我对我的naive真是太感动了
试想一下，因为路径压缩时，再次调用getf后，是要更新一部分值的。在数组上搞这些操作倒是挺快，然而在可持久化线段树里呢？每次找一个fa要\(log\)次，把这个节点更新又要新建log个节点，一共要循环找不满log次，理论上时间复杂度是\(O(Mlog^2N)\)的，但空间也是O\((Mlog^2N)\)的啊，乘个系数\((Mlog^2N×sizeof(int)×4\approx 800MB\),实际不满\()\)，随便算算就要炸空间了。。。。。。
那怎么办？去掉路径压缩不就得啦！并查集的按秩合并也是很优秀的方法，每次getf也只需要\(log\)次！时间复杂度\(O(Mlog^2N)\)并没有变。然后每次合并时只需要更新一个点，空间不就省下来了么？空间复杂度\(O(MlogN)\)。
以下是代码，数组版，叶子节点信息用结构体放了一下，略省点空间吧。。。
太弱了，不会封装，非递归版，可能略丑，见谅
#include<cstdio>
#define R register int
#define gc while(*++p<'0')
#define in(z) gc;z=*p&15;while(*++p>='0')z*=10,z+=*p&15
#define copy(id) lc[rt[i]=++cnt]=lc[rt[id]],rc[cnt]=rc[rt[id]];
//直接复制版本，不做改动
const int N=200009,M=4000009;
char I[M];
int n,i,cnt,cntl,rt[N],lc[M],rc[M],pos[M];
//cnt线段树节点，cntl叶子节点，pos记录对应叶子节点在数组中的位置
struct LEAF{
int fa,dep;
}leaf[N<<2];//叶子节点信息，dep用于按秩合并
inline LEAF*getf(R k){
R u,l,r,m;
while(1){
u=rt[i-1],l=1,r=n;
while(l<r)
{
m=(l+r)>>1;
if(k<=m)r=m,u=lc[u];
else l=m+1,u=rc[u];
}
if(k==leaf[pos[u]].fa)break;
k=leaf[pos[u]].fa;//循环找fa
}
return&leaf[pos[u]];//返回指针方便后续操作
}
void build(R&u,R l,R r){//建初始线段树
u=++cnt;
if(l==r){
leaf[pos[u]=++cntl]=(LEAF){l,0};
return;
}
R m=(l+r)>>1;
build(lc[u],l,m),build(rc[u],m+1,r);
}
inline void insert(R*u,R v,R k,LEAF newl){//更新节点
R l=1,r=n,m;
while(l<r) {
*u=++cnt;
m=(l+r)>>1;
if(k<=m)r=m,rc[*u]=rc[v],u=&lc[*u],v=lc[v];
else l=m+1,lc[*u]=lc[v],u=&rc[*u],v=rc[v];
}
leaf[pos[*u=++cnt]=++cntl]=newl;
}
int main(){
fread(I,1,sizeof(I),stdin);
register char*p=I-1;
register LEAF*af,*bf,*tmp;
R m,a,b;
in(n);in(m);
build(rt[0],1,n);
for(i=1;i<=m;++i){
gc;
switch(*p){
case '1':in(a);in(b);
af=getf(a),bf=getf(b);
if(af->fa==bf->fa){copy(i-1);break;}//已合并，跳过操作
if(af->dep>bf->dep)tmp=af,af=bf,bf=tmp;//按秩合并，确定bf为深度更大的
insert(&rt[i],rt[i-1],af->fa,(LEAF){bf->fa,af->dep});
if(af->dep==bf->dep)insert(&rt[i],rt[i],bf->fa,(LEAF){bf->fa,bf->dep+1});//注意更新深度
break;
case '2':in(a);copy(a);break;
case '3':in(a);in(b);copy(i-1);
putchar((getf(a)->fa==getf(b)->fa)|'0');
putchar('\n');
}
}
return 0;
}