洛谷P8867 [NOIP2022] 建造军营题解

题目链接：P8867 [NOIP2022] 建造军营

题意：

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

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

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

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

输入格式：

第一行包含两个正整数 \(n,m\)，分别表示城市的个数和双向道路的数量。

接下来 \(m\) 行，每行包含两个正整数 \(u_{i},v_{i}\)，描述一条连接 \(u_{i}\) 和 \(v_{i}\) 的双向道路。保证没有重边和自环。

输出格式:

输出一行包含一个整数，表示建造军营和看守道路的方案数对 \(1,000,000,007\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\)。

如果不是这道题我dp错了，也许我现在正在学校学文化课了（今天周二）。

注意到一个边双连通分量里边是可以随便选的，又因为图连通，因此考虑边双缩点后树形dp。

考场上我先想到的是设 \(f_{u,0/1}\) 表示 \(u\) 所在子树，\(u\) 不造/造的方案数。

事实上这个dp在转移和统计方案的时候会出现一些问题，或者说这个dp本身就是错的。下面开始讲正解。

设 \(f_{u,0/1}\) 表示 \(u\) 所在子树无/有军营的方案数，并强制 \(u\) 以外的节点不能造军营。

记 \(V_u,E_u,s_u\) 表示 \(u\) 缩点前的真实点数、真实边数和 \(u\) 所在子树的真实边数（ \(\sum E_u\) ）。

考虑转移。很显然 \(f_{u,0} = 2^{E_u} \times \prod_{v \in \operatorname{son}(u)} 2 f_{v,0}\) （注意要在 \(f_{u,1}\) 更新后再更新），然后是 \(f_{u,1}\) \[ f_{u,1} \leftarrow f_{u,0} \times f_{v,1}+f_{u,1} \times(2 f_{v, 0}+f_{v, 1}) \] 初始时 \(f_{u,0} = 2^{E_u}, ~f_{u,1} = 2^{V_u + E_u} - f_{u,0}\) 。

\(2\) 的次幂可以预处理一下。时间复杂度 \(\mathcal{O}(n + m)\) 。

然后这题就做完了，这道题告诉我们一个很重要的道理：状态千万不要设错！

考场代码魔改：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9+7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : x; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(5e5 + 15))
#define M ((int)(2e6 + 30))

vector<int> vec[N];
int n,m,res,pos = 1,head[N],f[N][2],pwd[M + N];
int ecnt,top,dfn[N],low[N],ecc[N],V[N],E[N],s[N],stk[N];
struct Edge { int u,v,next; } e[M];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void Tarjan(int u,int in_Edge)
{
    static int tim = 0; ++tim;
    dfn[u] = low[u] = tim; stk[++top] = u;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        if(!dfn[v])
        {
            Tarjan(v,i); down(low[u], low[v]);
        }else if(i != (in_Edge ^ 1)) down(low[u], dfn[v]);
    }
    if(low[u] == dfn[u])
    {
        ++ecnt;
        for(int p = 0; p != u; )
        { p = stk[top--]; ecc[p] = ecnt; ++V[ecnt]; }
    }
}
void dfs1(int u,int fa)
{
    s[u] = E[u];
    for(int v : vec[u]) if(v != fa)
    { dfs1(v,u); s[u] += s[v] + 1; }
}
void dfs2(int u,int fa)
{
    for(int v : vec[u]) if(v != fa)
    {
        dfs2(v,u);
        f[u][1] = f[u][1] * ((f[v][0] * 2 + f[v][1]) % mod) % mod;
        add(f[u][1], f[u][0] * f[v][1] % mod);
        f[u][0] = f[u][0] * f[v][0] * 2 % mod;
    }
    if(u == 1) add(res, f[u][1]);
    else add(res, f[u][1] * pwd[s[1] - s[u] - 1] % mod);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); read(m); pwd[0] = 1;
    for(int i = 1; i <= n + 2 * m; i++) pwd[i] = pwd[i - 1] * 2 % mod;
    for(int i = 1,u,v; i <= m; i++)
    {
        read(u); read(v);
        addEdge(u,v); addEdge(v,u);
    }
    Tarjan(1,0);
    for(int i = 2; i <= pos; i++)
    {
        int u = ecc[e[i].u], v = ecc[e[i].v];
        if(u != v) vec[u].push_back(v); else ++E[u];
    }
    for(int i = 1; i <= ecnt; i++)
    {
        E[i] >>= 1; f[i][0] = pwd[E[i]];
        add(f[i][1] = pwd[V[i] + E[i]], mod - f[i][0]);
    }
    dfs1(1,0); dfs2(1,0); write(res); pc('\n');
    return 0;
}