题目描述
小C和小G经常在一起研究搏弈论问题，有一天他们想到了这样一个游戏．
有一个 $n$ 个点 $m$ 条边的无向图，初始时每个节点有一个颜色，要么是黑色，要么是白色．现在他们对于每条边做出一次抉择：要么将这条边连接的两个节点都反色（黑变白，白变黑），要么不作处理．他们想把所有节点都变为白色，他们想知道在 $2^m$ 种决策中，有多少种方案能达成这个目标．
小G认为这个问题太水了，于是他还想知道，对于第 $i$ 个点，在删去这个点及与它相连的边后，新的答案是多少．
由于答案可能很大，你只需要输出答案对 $10^9 + 7$ 取模后的结果．
数据范围
$1 le T le 5, 1 le n, m le 10^5, 1 le u, v le n$
题解
考虑连通块内如果有奇数个黑点，则答案为 $0$
考虑只有一个连通块的情况，如果这个连通块是棵树，那么它只有一种染色方案。所以考虑建出这个连通块的 $dfs$ 树，那每条返祖边可以对答案有 $2$ 的贡献，即把这条返祖边连接的两个端点间的树边以及该返祖边一起染色，所以一个连通块的答案是 $2^{m-n+1}$ ，自然多个连通块的答案就是 $2^{m-n+c}$ ，其中 $c$ 为连通块个数
考虑删掉一个点，那就分割点或者非割点讨论一下，如果是割点，要注意连通块个数会增加，如果是单独一个点，则连通块个数会 $-1$ ，然后再计算一下有奇数个黑点的连通块个数有多少即可
代码
#include <bits/stdc++.h> using namespace std; const int N=2e5+5,P=1e9+7; char ch; int T,n,m,hd[N],V[N],nx[N],t,is[N],sz[N]; int a[N],dp[N],s[N],pw[N],A,C,R,g[N],sn[N]; void add(int u,int v){ nx[++t]=hd[u];V[hd[u]=t]=v; } void dfs(int x,int fr){ sz[x]=is[x];s[x]=dp[x]=dp[fr]+1; for (int i=hd[x];i;i=nx[i]){ if (V[i]==fr) continue; if (dp[V[i]]) s[x]=min(s[x],dp[V[i]]); else dfs(V[i],x),sn[x]++, sz[x]^=sz[V[i]], a[x]+=(s[V[i]]<dp[x]), s[x]=min(s[x],s[V[i]]); } } void work(int x,int fr){ int w=0,v,u=0,y=(fr>0),z=0; for (int i=hd[x];i;i=nx[i]) w++; if (a[x]==sn[x]){ v=A-sz[R]+(sz[R]^is[x]); if (!v) g[x]=pw[m-w-n+1+C]; } else{ for (int i=hd[x];i;i=nx[i]) if (dp[V[i]]==dp[x]+1 && s[V[i]]>=dp[x]) u+=sz[V[i]],z^=sz[V[i]],y++; u+=(sz[R]^z^is[x]);v=A-sz[R]+u; if (!v) g[x]=pw[m-w-n+1+C-1+y]; } for (int i=hd[x];i;i=nx[i]) if (dp[V[i]]==dp[x]+1) work(V[i],x); } void work(){ scanf("%d%d",&n,&m);t=C=A=0; for (int i=1;i<=n;i++) hd[i]=s[i]=sn[i]=a[i]=dp[i]=g[i]=0; for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y), add(x,y),add(y,x);t=0; for (int i=1;i<=n;i++) scanf(" %c",&ch),is[i]=(ch^48); for (int i=1;i<=n;i++) if (!dp[i]) dfs(i,0),A+=sz[i],C++; printf("%d",A?0:pw[m-n+C]); for (int i=1;i<=n;i++){ if (dp[i]==1){ if (!sn[i]){ if (A==sz[i]) g[i]=pw[m-n+C]; } else R=i,work(i,0); } printf(" %d",g[i]); } putchar(' '); } int main(){ pw[0]=1; for (int i=1;i<N;i++) pw[i]=(pw[i-1]<<1)%P; for (scanf("%d",&T);T--;work()); return 0; }