题目描述
小C和小G经常在一起研究搏弈论问题，有一天他们想到了这样一个游戏．
有一个
n
n
n 个点
m
m
m 条边的无向图，初始时每个节点有一个颜色，要么是黑色，要么是白色．现在他们对于每条边做出一次抉择：要么将这条边连接的两个节点都反色（黑变白，白变黑），要么不作处理．他们想把所有节点都变为白色，他们想知道在
2
m
2^m
2m 种决策中，有多少种方案能达成这个目标．
小G认为这个问题太水了，于是他还想知道，对于第
i
i
i 个点，在删去这个点及与它相连的边后，新的答案是多少．
由于答案可能很大，你只需要输出答案对
1
0
9
+
7
10^9 + 7
109+7 取模后的结果．
数据范围
1
≤
T
≤
5
,
1
≤
n
,
m
≤
1
0
5
,
1
≤
u
,
v
≤
n
1 \le T \le 5, 1 \le n, m \le 10^5, 1 \le u, v \le n
1≤T≤5,1≤n,m≤105,1≤u,v≤n
题解
考虑连通块内如果有奇数个黑点，则答案为
0
0
0
考虑只有一个连通块的情况，如果这个连通块是棵树，那么它只有一种染色方案。所以考虑建出这个连通块的
d
f
s
dfs
dfs 树，那每条返祖边可以对答案有
2
2
2 的贡献，即把这条返祖边连接的两个端点间的树边以及该返祖边一起染色，所以一个连通块的答案是
2
m
−
n
+
1
2^{m-n+1}
2m−n+1 ，自然多个连通块的答案就是
2
m
−
n
+
c
2^{m-n+c}
2m−n+c ，其中
c
c
c 为连通块个数
考虑删掉一个点，那就分割点或者非割点讨论一下，如果是割点，要注意连通块个数会增加，如果是单独一个点，则连通块个数会
−
1
-1
−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('\n');
}
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;
}
