[BZOJ5303][tarjan]HAOI2018：反色游戏

BZOJ5303

这题肯定是有关连通性的，考虑一个连通块，如果里面有偶数个黑点，则可以让它们两两组合，如果有奇数个就无解
如果是一棵树那么就只有一组解，加入非树边时异或一下就得到另一组解
所以一个连通块的$ans=2^{m-n+1}$ans=2m−n+1
删点就考虑一下它是不是割点就好了

Code：

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
const int N=100005;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
int n,m;
int sum,dcc,in[N],fa[N],dfn[N],low[N];
int sign,bel[N],rt,mi[N],val[N];
bool pt[N],col[N],w[N],tag[N],v[N];
int vis[N<<1],nxt[N<<1],head[N<<1],c[N<<1],cnt;
char s[N];
inline void add(int u,int v){vis[++cnt]=v;nxt[cnt]=head[u];c[cnt]=0;head[u]=cnt;}
void tarjan(int x,int e){
	dfn[x]=low[x]=++sign;
	w[x]=col[x];bel[x]=rt;pt[x]=0;
	for(int i=head[x];i;i=nxt[i]){
		if(i==(e^1)) continue;
		if(!dfn[vis[i]]){
			val[x]++;c[i]=c[i^1]=1;fa[vis[i]]=x;
			tarjan(vis[i],i);
			w[x]^=w[vis[i]];low[x]=min(low[x],low[vis[i]]);
			if(!e) continue;
			if(low[vis[i]]>=dfn[x]) pt[x]=1;
			else{
				c[e^1]=0;
				if(tag[x]) c[i]=0,v[x]^=w[vis[i]];
				else tag[x]=1;
			}
		}
		else low[x]=min(low[x],dfn[vis[i]]);
	}
}
inline int get_ans(int x);
inline void init(){
	memset(head,0,sizeof(head));
	memset(dfn,0,sizeof(dfn));
	memset(in,0,sizeof(in));
	memset(fa,0,sizeof(fa));
	memset(val,0,sizeof(val));
	memset(tag,0,sizeof(tag));
	memset(v,0,sizeof(v));
	sign=sum=dcc=0;cnt=1;
}
int main(){
	int t=read();
	while(t--){
		init();
		n=read();m=read();
		mi[0]=1;
		for(int i=1;i<=m;i++) mi[i]=mi[i-1]*2%mod;
		for(int x,y,i=1;i<=m;i++){
			x=read(),y=read();
			add(x,y);add(y,x);
			in[x]++,in[y]++;
		}
		scanf("%s",s+1);
		for(int i=1;i<=n;i++) col[i]=s[i]-'0';
		for(int i=1;i<=n;i++) if(!dfn[i]){
			++dcc,rt=i,tarjan(i,0);
			sum+=w[rt];
			pt[rt]=(val[rt]>1);
		}	
		cout<<(sum?0:mi[m-n+dcc])<<" ";
		for(int i=1;i<=n;i++) cout<<get_ans(i)<<" ";
		puts("");
	}
	return 0;
}
inline int get_ans(int x){
	if(!in[x]) return (sum-w[x])?0:mi[m-n+dcc];
	if(!pt[x]){
		int tmp=sum;
		if(w[bel[x]]) tmp--;
		if(w[bel[x]]^col[x]) tmp++;
		return tmp?0:mi[m-in[x]-n+1+dcc];
	}
	else{
		int tmp=sum,t=dcc-1;
		if(w[bel[x]]) tmp--;
		for(int i=head[x];i;i=nxt[i])
			if(c[i]){
				if(vis[i]==fa[x]) tmp+=w[bel[x]]^w[x];
				else if(low[vis[i]]<dfn[x]) tmp+=w[vis[i]]^w[bel[x]]^w[x]^v[x];
				else tmp+=w[vis[i]];
				t++;
			}
		return tmp?0:mi[m-in[x]-n+1+t];
	}
}