CCZ在2015年8月25日也就是初三暑假要结束的时候就已经能切这种题了%%%
学习了另一种启发式合并的方法，按秩合并，也就是按树的深度合并，实际上是和按树的大小一个道理，但是感觉（至少在这题上）更好处理一些。
然后就用可持久化线段树来维护这个可持久化数组，就能做到可持久化并查集，可持久化平衡树，可持久化之类的云云
3673不需要按秩合并，3674需要。。。用3674就能过俩，双倍经验双倍的幸福！
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #include<cmath> #include<map> #define ll long long using namespace std; const int maxn=200010,inf=1e9; struct poi{int lt,rt,fa,dep;}tree[maxn*40]; int n,m,ty,x,y,z,tot,sz; int root[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } void build(int &x,int l,int r) { x=++sz;if(l==r){tree[x].fa=l;return;} int mid=(l+r)>>1; build(tree[x].lt,l,mid);build(tree[x].rt,mid+1,r); } void update(int &x,int l,int r,int cx,int delta) { tree[++sz]=tree[x];x=sz; if(l==r){tree[x].fa=delta;return;} int mid=(l+r)>>1; if(cx<=mid)update(tree[x].lt,l,mid,cx,delta); else update(tree[x].rt,mid+1,r,cx,delta); } void add(int &x,int l,int r,int cx) { tree[++sz]=tree[x];x=sz; if(l==r){tree[x].dep++;return;} int mid=(l+r)>>1; if(cx<=mid)add(tree[x].lt,l,mid,cx); else add(tree[x].rt,mid+1,r,cx); } int query(int x,int l,int r,int cx) { if(l==r)return x; int mid=(l+r)>>1; if(cx<=mid)return query(tree[x].lt,l,mid,cx); else return query(tree[x].rt,mid+1,r,cx); } int gf(int k,int x){int xx=query(k,1,n,x);return tree[xx].fa==x?xx:gf(k,tree[xx].fa);} int main() { read(n);read(m); build(root[0],1,n); for(int i=1;i<=m;i++) { read(ty); root[i]=root[i-1]; if(ty==1) { read(x);read(y);x=gf(root[i],x);y=gf(root[i],y); if(tree[x].fa==tree[y].fa)continue; if(tree[x].dep>tree[y].dep)swap(x,y); update(root[i],1,n,tree[x].fa,tree[y].fa); if(tree[x].dep==tree[y].dep)add(root[i],1,n,tree[y].fa); } else if(ty==2)read(x),root[i]=root[x]; else read(x),read(y),printf("%d ",tree[gf(root[i],x)].fa==tree[gf(root[i],y)].fa); } return 0; }