[NOIP2022] 建造军营 题解

· · 题解

提供一种不需要边双缩点的做法，代码更为简洁，不过实际上本质也差不多。

对于这种无向简单图，一种很常用的 trick 是 DFS 出一个生成树，称为 DFS 树。无向图的 DFS 树有一个极好的性质，就是图中的非树边只能是返祖边。在很多题目中，我们可以依据这个性质使问题简化或变得更直观。

在本题中，先求出 DFS 树。我们称 u 为好节点，当且仅当 u 的子树中有至少一条连接到其父亲 fa 或 fa 的某个祖先的返祖边，否则称其为坏节点。

可以发现，对于一个好节点 u，无论删哪条边，u 子树中的每个节点都能与 u 子树外连通，故而 u-fa 这条边是否看守不会产生任何影响，且可将 u 子树的贡献全部算入 fa 子树中；而对于一个坏节点 u，看守 u-fa 这条边时，可将 u 子树的贡献全部算入 fa 子树中，不看守 u-fa 这条边时，敌人可删去 u-fa 这条边使 u 子树不再与外部联通，所以要么 u 子树内不建造任何军营，要么整个图上仅在 u 子树内建造军营。

接下来便可设计状态进行 DP。令 f_{u,0/1/2} 表示仅考虑 u 的子树，不建造任何军营 / 建造至少一座军营且 u 子树中不存在某个坏节点的子树内建造了军营 / 建造至少一座军营且 u 子树中存在某个坏节点的子树内建造了军营。

初始时，f_{u,0}=1,f_{u,1}=1,f_{u,2}=0。在转移时，我们可以依次遍历 u 所有的子节点 v，并利用当前 u 的 f_u 与 v 的 f_v 计算出加上 v 子树后的 f_u'。

对于一个好节点 v，转移方程为：

\begin{cases}f'_{u,0}=2f_{u,0}f_{v,0}\\f'_{u,1}=2f_{u,0}f_{v,1}+2f_{u,1}f_{v,0}+2f_{u,1}f_{v,1}\\f'_{u,2}=2f_{u,0}f_{v,2}+2f_{u,2}f_{v,0}\end{cases}

对于一个坏节点 v，转移方程为：

\begin{cases}f'_{u,0}=2f_{u,0}f_{v,0}\\f'_{u,1}=f_{u,0}f_{v,1}+2f_{u,1}f_{v,0}+f_{u,1}f_{v,1}\\f'_{u,2}=2f_{u,0}f_{v,2}+2f_{u,2}f_{v,0}+f_{u,0}f_{v,1}\end{cases}

对于所有 m-n+1 条返祖边，看守与否均不会产生任何影响，故最后答案为 2^{m-n+1}(f_{1,1}+f_{1,2})。

如何判断一个节点是否为好节点 / 坏节点？对于一条返祖边 d-u（d 为 u 的后代），可以发现这条边会使 d\sim u 简单路径上除了 u 的所有节点都变为好节点。利用差分实现即可。

时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll n,m,x,y,tot = 1,hd[500009],vis[500009],cnt[500009],f[500009][3];
bool ban[2000009];
struct st{ll x,y;}eg[2000009];
void addedge(ll u,ll v){eg[++ tot] = (st){v,hd[u]},hd[u] = tot;}
inline ll read(){
    ll s = 0,w = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
    while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    return s * w;
}
void dfs(ll u,ll fa){
    vis[u] = 1;
    for (ll i = hd[u];i;i = eg[i].y){
        ll v = eg[i].x;
        if (v == fa || ban[i]) continue;
        if (vis[v]){
            ban[i] = ban[i ^ 1] = 1;
            cnt[u] += 1,cnt[v] -= 1;
            continue;
        }
        dfs(v,u);
    }
}
void dfs2(ll u,ll fa){
    for (ll i = hd[u];i;i = eg[i].y){
        ll v = eg[i].x;
        if (v == fa || ban[i]) continue;
        dfs2(v,u),cnt[u] += cnt[v];
    }
}
void work(ll u,ll fa){
    f[u][0] = f[u][1] = 1,f[u][2] = 0;
    for (ll i = hd[u];i;i = eg[i].y){
        ll v = eg[i].x;
        if (v == fa || ban[i]) continue;
        work(v,u);
        ll tmp0 = 0,tmp1 = 0,tmp2 = 0;
        if (cnt[v]){
            tmp0 = 2 * f[u][0] * f[v][0] % mod;
            tmp1 = (2 * f[u][0] * f[v][1] % mod + 2 * f[u][1] * f[v][0] % mod + 2 * f[u][1] * f[v][1] % mod) % mod;
            tmp2 = (2 * f[u][0] * f[v][2] % mod + 2 * f[u][2] * f[v][0] % mod) % mod;
        }
        else{
            tmp0 = 2 * f[u][0] * f[v][0] % mod;
            tmp1 = (f[u][0] * f[v][1] % mod + 2 * f[u][1] * f[v][0] % mod + f[u][1] * f[v][1] % mod) % mod;
            tmp2 = (2 * f[u][0] * f[v][2] % mod + 2 * f[u][2] * f[v][0] % mod + f[u][0] * f[v][1] % mod) % mod;
        }
        f[u][0] = tmp0,f[u][1] = tmp1,f[u][2] = tmp2;
    }
}
int main(){
    n = read(),m = read();
    for (ll i = 1;i <= m;i += 1){
        x = read(),y = read();
        addedge(x,y),addedge(y,x);
    }
    dfs(1,0),dfs2(1,0),work(1,0);
    ll ans = (f[1][1] + f[1][2]) % mod;
    for (ll i = 1;i <= m - n + 1;i += 1) ans = (ans << 1) % mod;
    printf("%lld",ans);
    return 0;
}