[NOIP2022] 建造军营

题目链接

洛谷

LOJ

题目分析

将城市看做无向图，我们可以发现在同一个双联通分量中，不管哪一条道路被袭击，都可以保证该双联通分量中的军营可以互相抵达，所以我们可以先对图进行缩点。

完成缩点后，无向图被转化成了无根树，而接下来的操作类似 JSOI2018 的「潜入行动」,由于在树上求方案数，考虑 树上dp.

定义 $ dp[x][0/1] $ 表示在缩点后的无根树上，以点 $ x $ 为根节点的子树上全都不建造军营或所有建造的军营都安全的方案数，当对 $ x $ 的一个子树 $ to $ 进行决策时，考虑以下情况：

1、如果在 $ x $ 时选择都不建造，那么 $ to $ 也不能有军营，两点间的边随便看守不看守。

\[ dp[x][0] \leftarrow 2 \times dp[x][0] \times dp[to][0] \]

2、如果在 $ x $ 时选择建造，那么分为 3 种情况：

• $ x $ 在此之前没建造，而 $ to $ 建造了，此时中间的边必须看守来保证 $ x $ 的安全。
• $ x $ 在此之前建造了，而 $ to $ 没建造，则中间的边必须看守来保证 $ to $ 的安全。
• $ x $ 在此之前建造了，且 $ to $ 也建造了，则中间的边看不看守皆可。

分别对应如下转移方式： \[ \begin{split} dp[x][1] \leftarrow dp[x][0] \times dp[to][1] \\ dp[x][1] \leftarrow dp[x][1] \times dp[to][0] \\ dp[x][1] \leftarrow 2 \times dp[x][1] \times dp[to][1] \end{split} \]

上面是对于单个 $ to $ 的状态转移方程，实际上 $ x $ 的每一个子树是同等地位的，转移没有先后，总结一下得到如下方程：

\[ \begin{split} dp[x][0] = dp[x][0] \times \prod_{to}^{to \in son_x}{dp[to][0]} \\ dp[x][1] = dp[x][1] * \prod_{to}^{to \in son_x}{(dp[to][1] + 2 \times dp[to][0])} + dp[x][0] \times \prod_{to}^{to \in son_x}{dp[to][1]} \end{split} \]

在实际使用中需要把这个式子拆开这样好取模，为了让各个操作同时进行且不互相影响，需要使用临时变量记录一下。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 500010;

typedef long long ll;

struct Edge {
    int from;
    int to;
    int nxt;
} edge[MAXN * 4];
int head[MAXN];
int dfn[MAXN], col[MAXN], low[MAXN], siz[MAXN], tsize[MAXN];
int p2[MAXN * 2];
int n, m, cnt, depth, scnt;
bool cut[MAXN * 4];
vector<int> G[MAXN];
ll dp[MAXN][2];
ll ans;

void link(int u, int v)
{
    edge[++cnt].nxt = head[u];
    edge[cnt].to = v;
    edge[cnt].from = u;
    head[u] = cnt;
}

void tarjan(int x, int fa)
{
    dfn[x] = low[x] = ++depth;
    for (int i = head[x]; i; i = edge[i].nxt) {
        int to = edge[i].to;
        if (!dfn[to]) {
            tarjan(to, x);
            low[x] = min(low[x], low[to]);
            if (dfn[x] < low[to]) {
                // 双向边都要标记
                cut[i] = cut[((i + 1) ^ 1) - 1] = 1;
            }
        } else if (dfn[to] < dfn[x] && to != fa) {
            low[x] = min(low[x], dfn[to]);
        }
    }
}

void paint(int x)
{
    col[x] = scnt, siz[scnt]++;
    for (int i = head[x]; i; i = edge[i].nxt) {
        int to = edge[i].to;
        if (cut[i] or col[to]) continue;
        paint(to);
    }
}

void dfs(int x, int fa)
{
    tsize[x] = 1;
    dp[x][0] = 1, dp[x][1] = p2[siz[x]] - 1;
    for (auto to : G[x]) {
        if (to == fa) continue;
        dfs(to, x);
        tsize[x] += tsize[to];
        ll tmp0 = 0, tmp1 = 0;
        tmp0 = (2ll * dp[x][0] % MOD * dp[to][0] % MOD) % MOD;
        tmp1 = (2ll * dp[x][1] % MOD * dp[to][0] % MOD) % MOD;
        tmp1 = (tmp1 + (dp[x][1] % MOD * dp[to][1] % MOD) % MOD) % MOD;
        tmp1 = (tmp1 + (dp[x][0] % MOD * dp[to][1] % MOD) % MOD) % MOD;
        dp[x][0] = tmp0, dp[x][1] = tmp1;
    }
    int base = tsize[x];
    if (x == 1) base--;
    ans = (ans + dp[x][1] * p2[m - base] % MOD) % MOD;
}

int main()
{
    /* 预处理 2 的幂 */
    p2[0] = 1;
    for (int i = 1; i < MAXN * 2; i++) p2[i] = (p2[i - 1] << 1) % MOD;

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        link(a, b);
        link(b, a);
    }

    /* 求割边并进行缩点 */
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i, 0);
    }
    for (int i = 1; i <= n; i++) {
        if (!col[i]) {
            scnt++;
            paint(i);
        }
    }

    for (int i = 1; i <= m * 2; i++) {
        if (cut[i]) {
            G[col[edge[i].from]].push_back(col[edge[i].to]);
        }
    }

    dfs(1, 0);
    cout << ans << endl;

    return 0;
}