可持久化并查集模板（启发式合并）
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; typedef pair<int,pll> plll; const int N=2e5+10; struct node{ int l,r; int fa,cnt; node *ls,*rs; }*rt[N],pool[20*N]; int idx; node* build(int l,int r){ node *p=pool+(++idx); p->l=l,p->r=r; if(l==r){ p->fa=l,p->cnt=1; } else{ int mid=l+r>>1; p->ls=build(l,mid); p->rs=build(mid+1,r); } return p; } node *copynode(node *rt){ node *p=pool+(++idx); pool[idx]=*rt; return p; } node *change(node *rt,int l,int fa,int x){ node *p=copynode(rt); if(p->l==p->r){ p->cnt=x; p->fa=fa; return p; } int mid=p->l+p->r>>1; if(l<=mid) p->ls=change(p->ls,l,fa,x); else p->rs=change(p->rs,l,fa,x); return p; } node *query(node *rt,int x){ if(rt->l==rt->r){ return rt; } int mid=rt->l+rt->r>>1; if(x<=mid) return query(rt->ls,x); else return query(rt->rs,x); } node *find(node *rt,int x){ node *p=query(rt,x); if(p->fa==x) return p; else return find(rt,p->fa); } int main(){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; rt[0]=build(1,n); for(int i=1;i<=m;i++){ int opt; cin>>opt; rt[i]=rt[i-1]; if(opt==1){ int a,b; cin>>a>>b; node* pa=find(rt[i],a); node* pb=find(rt[i],b); //用线段树修改，因为要保留两个状态 if(pa->fa!=pb->fa){ if(pa->cnt>pb->cnt) swap(pa,pb); rt[i]=change(rt[i],pa->fa,pb->fa,0); rt[i]=change(rt[i],pb->fa,pb->fa,pa->cnt+pb->cnt); } } else if(opt==2){ int k; cin>>k; rt[i]=rt[k]; } else{ int a,b; cin>>a>>b; node *pa=find(rt[i],a); node *pb=find(rt[i],b); cout<<(pa->fa==pb->fa)<<endl; } } return 0; }