在分治的时候经常要还原并查集

用这个方法

struct UFS
{
	int fa[NN];
	int a[MM*10],b[MM*10],cnt;
	void save(int x)
	{++cnt;a[cnt]=fa[x];b[cnt]=x;}
	int getf(int x)
	{
		if(fa[x]==x)return x;
		int i=x,j;
		while(fa[x]!=x)x=fa[x];
		while(fa[i]!=i)
		{
			j=fa[i];
			save(i);
			fa[i]=x;
			i=j;
		}
		return x;
	}
	void merge(int a,int b)
	{
		int pa=getf(a),pb=getf(b);
		if(pa==pb)return;
		save(pa);p[pa]=pb;
	}
	void recover()
	{
		while(cnt)
		{
			p[b[cnt]]=a[cnt];
			cnt--;
		}
	}
}ufs;