2022 年牛客多校第八场 I 题题解

I Equivalence in Connectivity

题意：给定 $k$ 个 $n$ 的点的图。对于第 $i$ 个图，其由 $p_{i}$ 图删除或者新增一条边构成（保证 $p_{i} < i$ ），问这 $k$ 张图依据连通性可以分成多少组。 $n,k \leq 1\times 10^5$ 。

解法：显然可以注意到，对图的操作序列可以构成一棵树。首先简化问题：若每次只在上一张图上进行删除或新增操作，如何实现。

显然维护连通性可以用并查集，但是并查集无法维护删除操作，因而考虑只能添加不能删除。那么使用线段树分治：将这个操作序列建立一颗线段树，维护每条边出现的时间，必定是线段树上一段或几段的连续序列。然后再去遍历线段树，将添加的边下放到叶子节点，即可完成每个叶子节点的状态更新（并查集更新）。对于树上遍历的回溯操作，即是进行并查集的撤销操作。因而需要维护一个可撤销的并查集。

注意：只需要一个并查集即可。因为线段树在遍历的每一个时刻只会面对一个操作局面，因而只需要在这个状态下不断的添加边或者回溯到历史版本即可。

接下来要处理的问题是如何将这么多的状态的并查集去归类合并。一个精巧的办法是，给图上每个点一个随机权值，每个连通块的权值为连通块内所有点的权值异或和，再将所有连通块的权值和加起来作为哈希值。那么这样合并两个连通块只需要将两个连通块的权值异或起来即可，便于合并操作。此题卡单哈希，因而需要将这个随机数取得更大或者使用更多次的哈希。

最后，本问题是建立在树上的（操作序列为一棵树），但是容易发现，对于一条边的增加和删除，只不过是变成了子树内全部都要增加与子树内全部都要删除。那么只需要对操作树进行一次 dfs 序列化，即可将问题转化到序列上，因而整个问题就圆满解决。整体时间复杂度 $\mathcal O(n \log n)$ 。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define pb push_back
#define abs(x,y) (x<y?y-x:x-y)
using namespace std;
const LL N=1e5+3;
struct hh{
	LL to,nxt;
}e[N<<1];
struct kk{
	LL op,x,y;
	bool operator<(const kk &a) const{
	return x^a.x?x<a.x:y<a.y;}
}a[N],hsh[N];
struct zz{
	LL ld,lm,x,y;
};
LL n,m,k,num,fir[N],dfn[N],fa[N],siz[N],f1[N],f2[N],rev[N];
map<LL,LL>mp;
vector<LL>ans[N];
IL LL in(){
	char c;LL f=1;
	while((c=getchar())<'0'||c>'9')
	  if(c=='-') f=-1;
	LL x=c-'0';
	while((c=getchar())>='0'&&c<='9')
	  x=x*10+c-'0';
	return x*f;
}
IL LL mod(LL x){return x;}
IL LL find(LL x){
	while(x^fa[x]) x=fa[x];
	return x;
}
struct segment{
	#define ls k<<1
	#define rs k<<1|1
	#define pb push_back
	vector<kk>e[N<<2];vector<kk>fn[N<<2];
	void clear(LL k,LL l,LL r){
		e[k].clear(),fn[k].clear();
		if(l==r) return;
		LL mid=l+r>>1;
		clear(ls,l,mid),clear(rs,mid+1,r);
	}
	void ins(LL k,LL l,LL r,LL ll,LL rr,kk x){
		if(ll>rr) return;
		if(l>=ll&&r<=rr){e[k].pb(x);return;}
		LL mid=l+r>>1;
		if(ll<=mid) ins(ls,l,mid,ll,rr,x);
		if(rr>mid) ins(rs,mid+1,r,ll,rr,x);
	}
	IL void merge(LL x,LL y,LL k,LL &sum1,LL &sum2){
		LL fx=find(x),fy=find(y);
		if(fx^fy){
			if(siz[fx]<siz[fy]) swap(fx,fy);
			fn[k].pb((kk){f1[fx],fx,fy});
			sum1=mod(sum1-mod(f1[fx]+f1[fy])),
			sum2=mod(sum2-mod(f2[fx]+f2[fy])),
			fa[fy]=fx,siz[fx]+=siz[fy],f1[fx]^=f1[fy],f2[fx]^=f2[fy];
			sum1=mod(sum1+f1[fx]),sum2=mod(sum2+f2[fx]);
		}
	}
	void dfs(LL k,LL l,LL r,LL sum1,LL sum2){
		for(LL i=e[k].size()-1;~i;--i) merge(e[k][i].x,e[k][i].y,k,sum1,sum2);
		LL mid=l+r>>1;
		if(l==r) hsh[rev[l]]=(kk){0,sum1,sum2};
		else dfs(ls,l,mid,sum1,sum2),dfs(rs,mid+1,r,sum1,sum2);
		for(LL i=fn[k].size()-1;~i;--i){
			LL x=fn[k][i].x,y=fn[k][i].y;
			f2[x]^=f2[y],f1[x]^=f1[y],siz[x]-=siz[y],fa[y]=y;
		}
	}
}T;
IL void clear(){
	memset(fir+1,num=0,8*k);
	mp.clear(),T.clear(1,1,k);
	for(LL i=1;i<=k;++i) ans[i].clear();
}
IL void add(LL x,LL y){e[++num]=(hh){y,fir[x]},fir[x]=num;}
IL LL get(LL x,LL y){
	if(x<y) swap(x,y);
	return 1ll*(x-1)*n+y-1;
}
void dfs(LL u){
	rev[dfn[u]=++num]=u;LL cnt=get(a[u].x,a[u].y);
	if(u^1){
		if(a[u].op==1) mp[cnt]=num;
		else{
			T.ins(1,1,k,mp[cnt],num-1,a[u]);
			mp.erase(cnt);
		}
	}
	for(LL i=fir[u],v;v=e[i].to;i=e[i].nxt) dfs(v);
	if(u^1){
		if(a[u].op==1){
			T.ins(1,1,k,mp[cnt],num,a[u]);
			mp.erase(cnt);
		}
		else mp[cnt]=num+1;
	}
}
void solve(){
	char s[10];LL x,y,z,sum1=0,sum2=0;
	k=in(),n=in(),m=in();
	clear();
	for(LL i=1;i<=m;++i) x=in(),y=in(),mp[get(x,y)]=1;
	for(LL i=2;i<=k;++i){
		x=in(),scanf("%s",s+1),add(x,i);
		a[i]=(kk){(s[1]=='a')?1:-1,in(),in()};
	}
	num=0,dfs(1);
	for(map<LL,LL>:: iterator it=mp.begin();it!=mp.end();++it)
	  T.ins(1,1,k,it->second,k,(kk){0,it->first/n+1,it->first%n+1});
	for(LL i=1;i<=n;++i) fa[i]=i,siz[i]=1,f1[i]=rand(),f2[i]=rand(),sum1=mod(sum1+f1[i]),sum2=mod(sum2+f2[i]);
	T.dfs(1,1,k,sum1,sum2);LL cnt=0;map<kk,LL>mp;
	for(int i=1;i<=k;++i)
	  if(!mp.count(hsh[i])) mp[hsh[i]]=++cnt,ans[cnt].pb(i);
	  else ans[mp[hsh[i]]].pb(i);
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;++i){
		printf("%d ",ans[i].size());
		for(int j=0;j<ans[i].size();++j)
	  	printf("%d ",ans[i][j]);
	  putchar('\n');
	}
}
int main()
{
	srand(time(0));
	int T=in();
	while(T--) solve();
	return 0;
}