心路历程
50pts 黑周围选奇数条边，白周围选偶数条边，然后(nm^3)异或消元
初始是白是什么意思啊？
又或者删一个点有什么便捷算法？
SOL
貌似按顺序消元会得到一些良心结论
一条边(u,v)，我们把第v行变成第u行异或第v行就消掉了这条边（u,v合并后的星点）
若一条边的两个端点已经在一个连通分量里（消元的矩阵已经无这列为1的行了）
并查集维护，若联通则*2
扩展一些可得(ans=2^{m-n+联通分量个数})（若黑点个数为奇数则无解）
于是就维护联通分量个数和黑点奇偶即可，前者可以(tarjan)求割点，后者要难一些
对于后者，我们只用算出奇数黑点连通块的变化量(cb)即可
若非割点或为孤立点，根据这个点的黑白和所在连通块的黑色数量即可得知
若为割点
- 若所在连通块本来就有奇数个黑点，(cb--)（方便后面计算）
- 算出这个点删除后剩余连通块的奇黑个数，儿子连通块可直接在(tarjan)里算，(dfs)完后再处理这个点到根的连通块（异或即可得知是否有黑点）
时间复杂度(O(n))
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const int N=1e5+4,mod=1e9+7;
int n,m,tim,top,dh,ans;
int dfn[N],low[N],a[N],b[N],st[N],cb[N],divi[N],cut[N],mi[N];
char s[N];
vector<int>e[N];
void tarjan(int x,int fa){
dfn[x]=low[x]=++tim;
st[++top]=x;
int fl=0;
b[x]=a[x];
for(auto v:e[x]){
if(v==fa)continue;
if(!dfn[v]){
tarjan(v,x);
low[x]=min(low[x],low[v]);
a[x]^=a[v];
fl++;
if(low[v]>=dfn[x]){
cut[x]=1;
divi[x]++;
b[x]^=a[v];
if(a[v])cb[x]++;
}
}
else low[x]=min(low[x],dfn[v]);
}
if(fl<2&&!fa)cut[x]=divi[x]=cb[x]=0;
else if(!fa)divi[x]--;
}
inline void clear(){
tim=dh=0;
for(int i=1;i<N;i++)e[i].clear();
memset(cut,0,sizeof(cut));
memset(dfn,0,sizeof(dfn));
memset(divi,0,sizeof(divi));
memset(cb,0,sizeof(cb));
}
int main(){
int T=read();
mi[0]=1;
for(int i=1;i<N;i++)mi[i]=(mi[i-1]<<1)%mod;
while(T--){
clear();
n=read();m=read();
for(int i=1,u,v;i<=m;i++){
u=read();v=read();
e[u].push_back(v);e[v].push_back(u);
}
scanf("%s",s+1);
for(int i=1;i<=n;i++)a[i]=(s[i]^48);
ans=m-n;
for(int i=1,x;i<=n;i++)if(!dfn[i]){
tarjan(i,0);
ans++;
if(b[i])dh++;
if(e[i].empty())divi[i]=-1;
while(top){
x=st[top--];
if(cut[x]){
if(a[i])cb[x]--;
if(a[i]^b[x])cb[x]++;//到根节点的连通块还未判
}
else cb[x]=(s[x]=='1'?(a[i]?-1:1):0);
}
}
if(dh)cout<<"0 ";
else cout<<mi[ans]<<" ";
for(int i=1;i<=n;i++){
dh+=cb[i];ans+=divi[i]-e[i].size()+1;
if(dh)cout<<"0 ";
else cout<<mi[ans]<<" ";
dh-=cb[i];ans-=divi[i]-e[i].size()+1;
}
puts("");
}
return (0-0);
}