题意
给定 \(n\) 个点 \(m\) 条边的无向连通图。你需要给其中一些点和边染色，保证去掉任意一条未染色的边之后，所有染色的点都是连通的。问染色方案数对 \(10^9+7\) 取模的结果。
题解
注意到如果去除的边不是桥，则不会改变图的连通性，因此我们需要将桥和其它边分开考虑。先用 tarjan 找出所有桥，然后 dfs 统计每个 bcc 中点和边的数量。这样问题就转化为一个带点权的树上问题。
记第 \(i\) 个边双分量包含 \(se[i]\) 条边和 \(sp[i]\) 个节点。考虑树上 dp：
- \(f_{u,0}\) 表示 \(u\) 子树内没有染色的节点的方案数；
- \(f_{u,1}\) 表示 \(u\) 子树内有至少一个被染色的节点，并且这些节点都通过被染色的边和根节点相连的方案数；
- \(f_{u,2}\) 表示 \(u\) 子树内有至少一个被染色的点，它们在子树内通过被染色的边相互连通，但不与根节点相连的方案数；
答案就是 \(f_{rt,1}+f_{rt,2}\)。考虑转移（依次合并子树形式，直接按定义模拟即可）：
\[
\begin{align*}
f'_{u,0}&=f_{u,0}\times 2f_{v,0}\\
f'_{u,1}&=f_{u,0}\times f_{v,1}+f_{u,1}\times (f_{v,1}+2f_{v,0})\\
f'_{u,2}&=f_{u,0}\times (2f_{v,2}+f_{v,1})+f_{u,2}\times 2f_{v,0}
\end{align*}
\]
初值：
\[
\begin{align*}
f_{u,0}&=2^{se[u]}\\
f_{u,1}&=2^{se[u]}(2^{sp[u]}-1)\\
f_{u,2}&=0
\end{align*}
\]
注意取模。
AC 代码
| #include<iostream>
#define int long long
using namespace std;
const int N = 5E5 + 10;
const int M = 1E6 + 10;
const int MOD = 1e9 + 7;
struct Edge2 {
int u, v;
} edg[N];
int ne2;
struct Edge {
int v, next;
} pool[2 * M];
int ne, head[N];
void addEdge(int u, int v) {
pool[++ne] = {v, head[u]};
head[u] = ne;
}
int n, m;
int col[N], sp[N], se[N], bccCnt;
bool isbri[2 * M];
namespace bcc {
int dfn[N], low[N], dt;
void tarjan(int u, int fa) {
low[u] = dfn[u] = ++dt;
for(int i = head[u]; i; i = pool[i].next) {
int v = pool[i].v;
if(v == fa) continue;
if(!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]) {
isbri[i] = 1;
isbri[((i - 1) ^ 1) + 1] = 1;
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
void dfs(int u) {
col[u] = bccCnt;
sp[bccCnt]++;
for(int i = head[u]; i; i = pool[i].next) {
if(isbri[i]) continue;
int v = pool[i].v;
se[bccCnt]++;
if(!col[v]) dfs(v);
}
}
int fa[N];
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
fa[find(x)] = find(y);
}
void getScc() {
tarjan(1, 0);
for(int i = 1; i <= n; i++) {
if(!col[i]) {
++bccCnt;
dfs(i);
se[bccCnt] /= 2;
}
}
for(int i = 1; i <= n; i++) fa[i] = i;
for(int u = 1; u <= n; u++) {
for(int i = head[u]; i; i = pool[i].next) {
int v = pool[i].v;
if(col[u] != col[v] && find(col[u]) != find(col[v])) {
edg[++ne2] = {col[u], col[v]};
merge(col[u], col[v]);
}
}
}
for(int i = 1; i <= n; i++) head[i] = 0;
ne = 0;
if(ne2 + 1 != bccCnt) throw -1;
for(int i = 1; i <= ne2; i++) {
addEdge(edg[i].u, edg[i].v);
addEdge(edg[i].v, edg[i].u);
}
n = bccCnt;
}
}
int f[N][3];
namespace dp {
inline int qpow(int a, int b) {
int res = 1;
while(b) {
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void dfs(int u, int fa) {
f[u][0] = qpow(2, se[u]);
f[u][1] = qpow(2, se[u]) * (qpow(2, sp[u]) - 1 + MOD) % MOD;
for(int i = head[u]; i; i = pool[i].next) {
int v = pool[i].v;
if(v == fa) continue;
dfs(v, u);
f[u][2] = (f[u][0] * (2 * f[v][2] + f[v][1]) % MOD + 2 * f[u][2] * f[v][0] % MOD) % MOD;
f[u][1] = (f[u][0] * f[v][1] % MOD + f[u][1] * (f[v][1] + 2 * f[v][0]) % MOD) % MOD;
f[u][0] = 2 * f[u][0] * f[v][0] % MOD;
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
addEdge(u, v);
addEdge(v, u);
}
bcc::getScc();
dp::dfs(1, 0);
cout << (f[1][1] + f[1][2]) % MOD << endl;
return 0;
}
|