首先发现,非割边被切断后一定不会切断两个军营的连接。所以可以考虑边双缩点。
缩点后无向图变成一棵树,可以通过树上 DP 来统计答案。
记第 $u$ 个 E-dcc 的点数为 $E_u$,边数为 $V_u$,设所有 E-dcc 构成一棵以 $1$ 为根的树。
状态表示:$dp[u][0/1]$ 表示在以 $u$ 为根的子树内,建或者不建造军营的情况数,且在这个子树内所有军营之间的路径全部被守护。
状态计算:
1. 初始状态:$dp[u][0] = 2^{E_u}$,因为同一个边双内切断任意一条边不改变连通性,所以可以任意保护。同理容斥可得 $dp[u][1] = 2^{V_u+E_u} - 2^{E_u}$。
2. 状态转移:
- $dp[u][0] = dp[u][0] \times (2 \times dp[v][0])$,不建造军营则每条边都可以守护或者不守护。
- $dp[u][1]$ 可以划分为两部分:
1. 点 $u$ 内不建造军营,则子树 $v$ 内必须建造军营,情况数为 $2^{E_u} \times dp[v][1]$
2. 点 $u$ 建造军营,则子树 $v$ 建造或者不建造来决定边保护或者不保护,情况数为 $dp[u][1] \times (dp[v][1] + 2 \times dp[v][0])$
因此 $dp[u][1] = 2^{E_u} \times dp[v][1] + dp[u][1] \times (dp[v][1] + 2 \times dp[v][0]) $
3. 答案统计:
分别统计每个子树 $u$ 对答案的贡献,子树 $u$ 必须建造军营,子树外不能建造军营,这样答案可以不重复不遗漏。然后关于边的守护,子树内的情况已经算在总情况内,子树外的边可以任意守护或者不守护。注意如果守护了 $u$ 点到其父亲的边,则这种情况会在统计其父亲节点所在的子树对答案的贡献时重复计算。
边数可以用子树和来计算。具体的,子树 $u$ 内的边数 $s[u] = E_u \sum (s[v] + 1)$。
综上所述,子树 $u$ 对答案的贡献是 $dp[u][1] \times (s[1] - s[u] - 1)$,注意根节点没有父节点,要单独统计。
参考题解:Chy12321’s Blog NOIP2022 T3 建造军营。
参考代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5, M = 2e6 + 5, mod = 1e9 + 7;
struct graph
{
int head[N], to[M], nxt[M], ecnt, vcnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
} g1, g2;
int n, m;
int dcc[N], dcc_e[N], dcc_v[N];
int dfn[N], low[N], tim;
int stk[N], top;
void tarjan(int u, int ine)
{
dfn[u] = low[u] = ++tim;
stk[++top] = u;
for (int e = g1.head[u]; e; e = g1.nxt[e])
{
int v = g1.to[e];
if (!dfn[v])
tarjan(v, e), low[u] = min(low[u], low[v]);
else if ((e ^ 1) != ine)
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
int x = ++g2.vcnt;
int v = stk[top];
do
{
v = stk[top--];
dcc_v[x]++;
dcc[v] = x;
} while (v != u);
}
}
int qmi(int x, int p)
{
int res = 1 % mod;
while (p)
{
if (p & 1)
res = res * x % mod;
x = x * x % mod;
p >>= 1;
}
return res;
}
int dp[N][2], s[N];
void dfs(int u, int fa)
{
s[u] = dcc_e[u];
for (int e = g2.head[u]; e; e = g2.nxt[e])
{
int v = g2.to[e];
if (v == fa)
continue;
dfs(v, u);
dp[u][1] = (dp[u][0] * dp[v][1] % mod + dp[u][1] * (dp[v][1] + 2 * dp[v][0] % mod) % mod) % mod;
dp[u][0] = dp[u][0] * (2 * dp[v][0] % mod) % mod;
s[u] += s[v] + 1;
}
}
signed main()
{
ios::sync_with_stdio(false);
#ifdef DEBUG
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
// Don't stop. Don't hide. Follow the light, and you'll find tomorrow.
cin >> n >> m;
g1.ecnt = 1, g1.vcnt = n;
for (int i = 1, u, v; i <= m; i++)
{
cin >> u >> v;
g1.add(u, v), g1.add(v, u);
}
tarjan(1, 0);
for (int u = 1; u <= n; u++)
{
for (int e = g1.head[u]; e; e = g1.nxt[e])
{
int v = g1.to[e];
int du = dcc[u], dv = dcc[v];
if (du != dv)
g2.add(du, dv);
else
dcc_e[du]++;
}
}
for (int u = 1; u <= g2.vcnt; u++)
{
dcc_e[u] /= 2;
dp[u][0] = qmi(2, dcc_e[u]);
dp[u][1] = qmi(2, dcc_v[u] + dcc_e[u]) - dp[u][0];
}
dfs(1, 0);
int ans = dp[1][1];
for (int u = 2; u <= g2.vcnt; u++)
ans = (ans + dp[u][1] * qmi(2, s[1] - s[u] - 1)) % mod;
cout << ans << endl;
return 0;
}