建造军营 NOIP 2022

WZH2026-05-302026-05-31

[NOIP2022] 建造军营

题目： [NOIP2022] 建造军营。

这是我第一个自己写出来的组合数学和树形 DP 的题目。

题目内容：

给定 $n$ 个点 $m$ 条边的无向联通简单图，可以在任意多个点（至少一个）建立军营，在任意多条边建立士兵。

求有多少种建造方案数使得任意切断一条没有士兵的边后，所有军营依然联通。

$n \le 5\times 10^5,m\le 10^6$ 。

时间限制 $1.00s$ ，内存限制 $512.00MB$ ，期望复杂度 $O(n+m)$ 。

首先，看到这个题目，这其中 所有军营依然联通 的限制让我们想到边双缩点后在树上求解，这是因为在边双中任意断边后边双内任意两点仍然联通。

问题就转变为了在一个树上求解。

设一个边双 $i$ 内有 $a_i$ 个点和 $b_i$ 条边。

如果设 $f_i$ 表示以 $i$ 为根的子树内的答案， $\sum b_i$ 为以 $i$ 为根的子树内的边数，那么这里我们需要分情况讨论：

如果不在 $i$ 建立军营：

那么对于 $i$ 的每个儿子 $u$ ，我们都可以在这个子树内选择建立军营（由于 $f_i$ 的定义，这里会至少建立一个）或者不建立军营。如果建立军营，那么方案数是 $f_u$ ；否则不建立军营，那么这个子树内的边和 $u$ 连向 $i$ 的边都可以建立或不建立士兵，方案数为 $2^{1+\sum b_u}$ 。总方案数就是 $\displaystyle\prod (2^{1+\sum b_u} + f_u)$ 。

然而，由于至少建立一个军营，所以要减去不建立军营的 $2^{\sum b_i}$ 中方案。

并且，当我只在一个子树 $u$ 内建立军营时， $u$ 和 $i$ 之间的边其实是可以不建立士兵的。这时我们就要加上这一部分代价，称作补偿贡献。这种情况下，子树 $u$ 的方案数为 $f_u$ ，其余边可以任意选择，方案数为 $f_u2^{\sum b_i-\sum b_u}$ 。但注意，由于我们原来已经累加了 $f_u2^{\sum b_i-\sum b_u-1}$ 的代价了，所以这里只累加 $f_u2^{\sum b_i-\sum b_u-1}$ ，总的补偿贡献就是 $\displaystyle\sum f_u2^{\sum b_i-\sum b_u-1}$ 。

这种情况的总方案数就是全方案加补偿贡献减去不合法方案。

如果在 $i$ 建立军营：

首先，由于 $i$ 是一个边双，单独在 $i$ 建立军营的方案数为 $(2^{a_i}-1)2^{b_i}$ 。然后我们需要考虑子树。

对于子树 $u$ ，他的贡献和上面是一样的，为 $2^{1+\sum b_u}+f_u$ 。这样的总贡献为 $(2^{a_i}-1)2^{b_i}\displaystyle\prod (2^{1+\sum b_u} + f_u)$ 。

其次，由于我们已经在 $i$ 建立军营了，所以没有不合法方案。

然后，由于所有军营都要保证和 $i$ 联通，对于子树 $u$ ， $u$ 到 $i$ 的边在 $u$ 建立军营的情况下必须建立士兵，所以没有补偿贡献。

也就是说，总方案数就是全方案。

最后累加这两种情况的答案就行。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1000010,P=1000000007;
int n,m,low[N],dfn[N],idx,f[N],s[N],top,dcc[N],cnt,a[N],b[N],book[N],sz[N],pw[N];
vector<int>v[N],g[N];
void dfs(int x,int fa){
    low[x]=dfn[x]=++idx;
    s[++top]=x;
    for(int u:g[x]){
        if(!dfn[u]){
            dfs(u,x);
            low[x]=min(low[x],low[u]);
        }
        else if(u!=fa)low[x]=min(low[x],dfn[u]);
    }
    if(low[x]==dfn[x]){
        int t;
        cnt++;
        do{
            t=s[top--];
            dcc[t]=cnt;
            a[cnt]++;
        }while(t!=x);
    }
}
void getb(int x,int cl){
    book[x]=1;
    for(int j:g[x]){
        if(dcc[j]!=cl)continue;
        if(!book[j])getb(j,cl);
        b[cl]++;
    }
}
void dfs2(int x,int fa){
    int cnt1=1;
    sz[x]=b[x];
    for(int u:v[x]){
        if(u==fa)continue;
        dfs2(u,x);
        sz[x]+=sz[u]+1;
        cnt1=1ll*(pw[1+sz[u]]+f[u])%P*cnt1%P;
    }
    f[x]=(1ll*cnt1*pw[b[x]]%P-pw[sz[x]]+P)%P;
    for(int u:v[x]){
        if(u==fa)continue;
        (f[x]+=1ll*f[u]*pw[sz[x]-sz[u]-1]%P)%=P;
    }
    (f[x]+=1ll*cnt1*(pw[a[x]]-1+P)%P*pw[b[x]]%P)%=P;
}
int main(){
    cin>>n>>m;
    pw[0]=1;
    for(int i=1;i<=1000000;i++)pw[i]=2ll*pw[i-1];
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++){
        for(int j:g[i]){
            int x=dcc[i],y=dcc[j];
            if(x!=y)v[x].push_back(y);
        }
    }
    for(int i=1;i<=n;i++)if(!book[i])getb(i,dcc[i]),b[dcc[i]]>>=1;
    dfs2(1,0);
    cout<<f[1];
    return 0;
}

但是这样是有问题的！

原因是，在转移 $i$ 的时候， $f_i$ 包含了两种方案的贡献：一种是正常贡献（即全方案减去不合法方案），一种是补偿贡献！

这个对于子树 $u$ 同样适用。

我们来看一看 $u$ 的补偿贡献究竟能不能贡献到 $f_i$ 里。

由于这个是补偿贡献，所以这些方案都是 $u$ 的子树的贡献！设为 $u$ 的子树 $v$ 的贡献，那么在 $u$ 向 $i$ 贡献的时候，由于是补偿贡献， $u$ 和 $v$ 的连边没有建立士兵！此时根据题意，这种情况是不合法的。

也就是说，补偿贡献不能直接累加到 $f_i$ 里面。

有一个比较直观的例子（样例太简单了，缩点后只有两层，无法体现这个错误）：

1
2
3

3 2
1 2
2 3

这时，为了保证转移，我们需要更改 $f_i$ 的定义为没有补偿贡献的方案数，即，所有军营到 $i$ 的路径上的边都被建立士兵的方案数。

那这个新的 $f_i$ 的转移就十分简单了，只需要扔掉原来的转移中的补偿贡献就行了。

但是我们还是要求答案的。所以我们额外定义 $F_i$ 为 $i$ 子树内的答案。

我们考虑怎么转移 $F$ 。

首先我们是可以直接让 $F_i=f_i$ 的。那么此时 $F$ 需要累加上补偿贡献。然后，由于当 $i$ 建造军营时没有补偿贡献，所以我们只考虑 $i$ 没有建造军营时的情况。

接着，这个时候的方案数也是形如 $\displaystyle\sum f_u2^{\sum b_i-\sum b_u}$ 的。由于原来的 $f$ 对应现在的 $F$ ，所以我们需要把贡献改写成 $\displaystyle\sum F_u2^{\sum b_i-\sum b_u}$ 。

然后，由于原来的补偿贡献可以写成那样的形式的前提是因为原贡献中已经累加了一部分了。这里已经让 $F$ 累加了 $f$ 了，但是 $f$ 累加的是有关 $f$ 的式子，而 $F$ 要累加的是有关 $F$ 的式子，所以我们还要减去这部分，即 $\displaystyle\sum f_u2^{\sum b_i-\sum b_u-1}$ 。

最终就有 $F_i=f_i+\displaystyle\sum F_u2^{\sum b_i-\sum b_u}-\displaystyle\sum f_u2^{\sum b_i-\sum b_u-1}$ 。

答案就是根的 $F$ 值。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1003010,P=1000000007;
int n,m,low[N],dfn[N],idx,f[N],s[N],top,dcc[N],cnt,a[N],b[N],book[N],sz[N],pw[N],F[N];
vector<int>v[N],g[N];
void dfs(int x,int fa){
    low[x]=dfn[x]=++idx;
    s[++top]=x;
    for(int u:g[x]){
        if(!dfn[u]){
            dfs(u,x);
            low[x]=min(low[x],low[u]);
        }
        else if(u!=fa)low[x]=min(low[x],dfn[u]);
    }
    if(low[x]==dfn[x]){
        int t;
        cnt++;
        do{
            t=s[top--];
            dcc[t]=cnt;
            a[cnt]++;
        }while(t!=x);
    }
}
void getb(int x,int cl){
    book[x]=1;
    for(int j:g[x]){
        if(dcc[j]!=cl)continue;
        if(!book[j])getb(j,cl);
        b[cl]++;
    }
}
void dfs2(int x,int fa){
    int cnt1=1;
    sz[x]=b[x];
    for(int u:v[x]){
        if(u==fa)continue;
        dfs2(u,x);
        sz[x]+=sz[u]+1;
        cnt1=1ll*(pw[1+sz[u]]+f[u])%P*cnt1%P;
    }
    f[x]=(1ll*cnt1*pw[b[x]]%P-pw[sz[x]]+P)%P;
    (f[x]+=1ll*cnt1*(pw[a[x]]-1+P)%P*pw[b[x]]%P)%=P;
    F[x]=f[x];
    for(int u:v[x]){
        if(u==fa)continue;
        (F[x]+=P-1ll*f[u]*pw[sz[x]-sz[u]-1]%P)%=P;
        (F[x]+=1ll*F[u]*pw[sz[x]-sz[u]]%P)%=P;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    pw[0]=1;
    for(int i=1;i<=1001110;i++)pw[i]=2ll*pw[i-1]%P;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++){
        for(int j:g[i]){
            int x=dcc[i],y=dcc[j];
            if(x!=y)v[x].push_back(y);
        }
    }
    for(int i=1;i<=n;i++)if(!book[i])getb(i,dcc[i]),b[dcc[i]]>>=1;
    dfs2(1,0);
    cout<<F[1];
    return 0;
}