对于像UVA 11987 Almost Union-Find这样的题目，要求把一个元素从一个集合中剥离的情况，我们只需要新建一个节点然后……….

还是看代码吧：

inline void move(int x,int y)     // 把x从y集合中剥离{    int fx = find(id[x]),fy = find(id[y]);    if(fx == fy)  return ;    cnt[fx] --,sum[fx] -= x;    id[x] = ++ tot;		// 可持久化    f[id[x]] = fy;  cnt[fy] ++,sum[fy] += x;}

这种方法主要是利用id[]，在最初时id[i] = i，随着移动i，id[i]也在变化，在访问i时，我们需直接用id[i]代替。

对于 BZOJ  3674: 可持久化并查集加强版 我们就不能cheat 了，我们需要真的可持久化了。

因为并查集的所有信息都保存在fa[]里，所以，我们只需要用可持久化线段树实现一个可持久化数组就可以了。

ACCode：

#include<cstdio>#include<iostream>using namespace std;inline int read(){    int x=0;char ch=getchar();    while(ch>‘9‘||ch<‘0‘)ch=getchar();    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x;}int n,m,sz,last;int root[200005],ls[10000005],rs[10000005],v[10000005],deep[10000005];void build(int &k,int l,int r){	if(!k)k=++sz;	if(l==r){v[k]=l;return;}	int mid=(l+r)>>1;	build(ls[k],l,mid);	build(rs[k],mid+1,r);}void modify(int l,int r,int x,int &y,int pos,int val){	y=++sz;	if(l==r){v[y]=val;return;}	ls[y]=ls[x];rs[y]=rs[x];	int mid=(l+r)>>1;	if(pos<=mid)		modify(l,mid,ls[x],ls[y],pos,val);	else modify(mid+1,r,rs[x],rs[y],pos,val);}int query(int k,int l,int r,int pos){	if(l==r)return k;	int mid=(l+r)>>1;	if(pos<=mid)return query(ls[k],l,mid,pos);	else return query(rs[k],mid+1,r,pos);}void add(int k,int l,int r,int pos){	if(l==r){deep[k]++;return;}	int mid=(l+r)>>1;	if(pos<=mid)add(ls[k],l,mid,pos);	else add(rs[k],mid+1,r,pos);}int find(int k,int x){    int p=query(k,1,n,x);	if(x==v[p])return p;    return find(k,v[p]);}int main(){	n=read();m=read();	build(root[0],1,n);	int f,k,a,b;	for(int i=1;i<=m;i++)	{		f=read();		if(f==1)		{			root[i]=root[i-1];			a=read();b=read();a=a^last;b=b^last;			int p=find(root[i],a),q=find(root[i],b);			if(v[p]==v[q])continue;			if(deep[p]>deep[q])swap(p,q);			modify(1,n,root[i-1],root[i],v[p],v[q]);			if(deep[p]==deep[q])add(root[i],1,n,v[q]);		}		if(f==2)		{k=read();k=k^last;root[i]=root[k];}		if(f==3)		{			root[i]=root[i-1];			a=read();b=read();a=a^last;b=b^last;		    int p=find(root[i],a),q=find(root[i],b);			if(v[p]==v[q])last=1;			else last=0;			printf("%d\n",last);		}	}	return 0;}