P8867 [NOIP2022] 建造军营

P8867 [NOIP2022] 建造军营

A 国与 B 国正在激烈交战中，A 国打算在自己的国土上建造一些军营。

A 国的国土由 \(n\) 座城市组成，\(m\) 条双向道路连接这些城市，使得任意两座城市均可通过道路直接或间接到达。A 国打算选择一座或多座城市（至少一座），并在这些城市上各建造一座军营。

众所周知，军营之间的联络是十分重要的。然而此时 A 国接到情报，B 国将会于不久后袭击 A 国的一条道路，但具体的袭击目标却无从得知。如果 B 国袭击成功，这条道路将被切断，可能会造成 A 国某两个军营无法互相到达，这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路（可以是一条或多条，也可以一条也不看守)，A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。

A 国希望制定一个建造军营和看守道路的方案，使得 B 国袭击的无论是 A 国的哪条道路，都不会造成某两座军营无法互相到达。现在，请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多，你只需要输出其对 \(\left(10^{9}+7\right)\) 取模的值即可。两个方案被认为是不同的，当且仅当存在至少一 座城市在一个方案中建造了军营而在另一个方案中没有，或者存在至少一条道路在一个 方案中被派兵看守而在另一个方案中没有。

对所有数据，保证 \(1 \leq n \leq 5 \times 10^5\)， \(n - 1 \leq m \leq 10^6\)， \(1 \leq u_i, v_i \leq n\)， \(u_i \neq v_i\)。

只有 B 国炸毁了图的割边，才会使得图不连通，进而可能会导致军营不连通。也就是说，A 国可以随意地看守或不看守不是割边的边。因此想到边双缩点后树形 DP。

已经缩了点，再思考：究竟要在缩点后形成的树上求什么？

令 \(V_u\) 表示双连通分量 \(u\) 中的点数，\(E_u\) 表示双连通分量 \(u\) 中的边数，若有 \(n\) 个双连通分量，问题转化为：

给定一棵无根树，每个结点 \(u\) 有 \(2^{E_u}\) 种不建造军营的方案和 \((2^{V_u + E_u} - 2^{E_u})\) 种建造军营的方案。求共有多少种建造军营的方案（不能不建）。这里假定 1 号结点为树根。

令 \(f(u, 0/1)\) 表示以 \(u\) 为根的子树中没有/有军营的方案数。发现每种状态所涵盖的情况过多，根本不好转移。这时，对状态增添限制：

令 \(f(u, 0/1)\) 表示以 \(u\) 为根的子树中没有/有军营的方案数，若有军营，则所有的军营必须通过已经派兵看守的边与 \(u\) 连通。

在想转移之前，为了防止做无用功，最好先想该如何统计答案。

对于每个结点 \(u\)，强制 \(u\) 子树外的所有点都不建军营，同时强制不选 \(fa_u \to u\) 的边，再累加方案数，即可保证不重不漏。

令 \(s(u)\) 表示以 \(u\) 为根节点的子树内边数，即 \(s(u) = E_u + \sum_{v \in son(u)} (s(v) + 1)\)，则有 \(ans \leftarrow f(u, 1) \times 2^{s(1) - s(u) - 1}\)。

特殊地，对于 1 号结点，不存在 \(fa_1 \to 1\) 的边，此时 \(ans \leftarrow f(1, 1)\)。

明确了答案如何统计，接下来考虑转移：

显然地，\(f(u, 0) = 2^{E_u} \times \prod_{v \in son(u)} 2f(v, 0)\)，难点在 \(f(u, 1)\) 的转移上。考虑每新增一个子节点 \(v\) 对 \(f(u, 1)\) 产生的贡献：

  • 若新增前都还未建造一个军营，则以 \(v\) 为根的子树中必须有军营，即 \(f(u, 1) \leftarrow f(u, 0) \times f(v, 1)\)。
  • 若新增前已经建造过军营，则以 \(v\) 为根的子树中有没有军营皆可，且当以 \(v\) 为根的子树中没有军营时，\(v\) 是否与 \(u\) 连通皆可，即 \(f(u, 1) \leftarrow f(u, 1) \times [2f(v, 0) + f(v, 1)]\)。

综上，\(f(u, 1) \leftarrow f(u, 0) \times f(v, 1) + f(u, 1) \times [2f(v, 0) + f(v, 1)]\)。

初始时，\(f(u, 0) = 2^{E_u}\)， \(f(u, 1) = 2^{V_u + E_u} - 2^{E_u}\)。

实现 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10, MAXM = 1e6 + 10, mod = 1e9 + 7;
int n, m, bccidx;
int head[MAXN], head2[MAXN];
int idx, top, stk[MAXN], dfn[MAXN], low[MAXN], bcc[MAXN];
int deg[MAXN], V[MAXN], E[MAXN], s[MAXN];
bitset<MAXN> vis;
ll ans, f[MAXN][2];
struct edge
{
    int v, nxt;
} e[MAXM << 1], e2[MAXM << 1];
void addedge(int u, int v)
{
    static int edge_cnt = 0;
    e[++edge_cnt] = {v, head[u]};
    head[u] = edge_cnt;
}
void addedge2(int u, int v)
{
    static int edge_cnt = 0;
    e2[++edge_cnt] = {v, head2[u]};
    head2[u] = edge_cnt;
}
void tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++idx, vis[stk[++top] = u] = 1;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (v == fa)
            continue;
        if (!dfn[v])
            tarjan(v, u), low[u] = min(low[u], low[v]);
        else if (vis[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        bccidx++;
        int x;
        do
        {
            vis[x = stk[top--]] = 0, bcc[x] = bccidx;
            V[bccidx]++;
        } while (x != u);
    }
}
ll qpow(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void calc(int u, int fa)
{
    s[u] = E[u];
    for (int i = head2[u], v; i; i = e2[i].nxt)
    {
        v = e2[i].v;
        if (v == fa)
            continue;
        calc(v, u);
        s[u] += s[v] + 1;
    }
}
void dfs(int u, int fa)
{
    for (int i = head2[u]; i; i = e2[i].nxt)
    {
        int v = e2[i].v;
        if (v == fa)
            continue;
        dfs(v, u);
        f[u][1] = (f[u][1] * (((f[v][0] << 1) + f[v][1]) % mod) % mod + f[u][0] * f[v][1] % mod) % mod;
        f[u][0] = f[u][0] * ((f[v][0] << 1) % mod) % mod;
    }
    if (u == 1)
        ans = (ans + f[u][1]) % mod;
    else
        ans = (ans + f[u][1] * qpow(2, s[1] - s[u] - 1)) % mod;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        addedge(u, v), addedge(v, u);
    }
    tarjan(1, 0);
    for (int u = 1; u <= n; u++)
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            if (bcc[u] != bcc[v])
                addedge2(bcc[u], bcc[v]);
            else
                E[bcc[u]]++;
        }
    for (int i = 1; i <= bccidx; i++)
    {
        E[i] >>= 1; // 无向边，一条边会算两次，去重
        f[i][0] = qpow(2, E[i]);
        f[i][1] = qpow(2, V[i] + E[i]) - f[i][0];
    }
    calc(1, 0);
    dfs(1, 0);
    cout << ans;
    return 0;
}