P8867 [NOIP2022] 建造军营 题解

· · 个人记录

题意：

给定一张连通无向图，并在至少一个点建军营和若干条边上派兵驻守，求有多少种方案满足切断任意一条未被派兵驻守的边，都不会使所有军营两两不能到达，方案数对 10^9+7 取模。

### 思路： 考虑边双缩点，形成一棵树。 设缩点后第 $i$ 块内点数为 $a_i$，边数为 $e_i$。 令 $f_{u,0}$ 表示以 $u$ 为根的子树内不建军营的方案数，$f_{u,1}$ 表示以 $u$ 为根子树内有军营，且所有军营到 $u$ 之间所有边均派兵把守的方案数。 我们考虑在枚举 $u$ 的子节点 $v$ 时对 $f_u$ 值产生的影响： $f_{u,0}$ 转移是显然的，有 $$f_{u,0} \leftarrow f_{u,0} \times 2f_{v,0}$$ 其中系数 $2$ 表示这条边可选可不选。 $f_{u,1}$ 转移较为复杂： 若到当前为止未建军营，则有 $$f_{u,1} \leftarrow f_{u,0} \times f_{v,1}$$ 若建过军营，则 $v$ 中有没有军营均可： $$f_{u,1} \leftarrow f_{u,1} \times (2f_{v,0}+f_{v,1})$$ $f_{u,0}$ 初始化为 $2^{e_u}$，$f_{u,1}$ 初始化为 $2^{a_u+e_u}-2^{e_u}$。 考虑如何计算答案，对于每个点 $u$，令所选点均在 $u$ 子树内，且强制不选到其父亲这条边，那么贡献为 $$f_{u,1} \times 2^{siz_1-siz_u-1}$$ 其中 $siz_u=e_u+\sum_{v \in son_u} (siz_v+1)

特殊的，根节点贡献为 f_{1,1}。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5e5+5;
const int M=1e6+5;
const int mod=1e9+7;
struct edge
{
    int next,to;
}e[M<<1],mp[M<<1];
bool vis[N];
int n,m,cnt,seg,tot,top,ans,in[N],dfn[N],low[N];
int col[N],st[N],sz[N],ed[N],f[N][2],sum[N];
int cnt2,in2[N];
int read()
{
    int res,f=1;
    char ch;
    while((ch=getchar())<'0'||ch>'9')
    if(ch=='-')
    f=-1;
    res=ch^48;
    while((ch=getchar())>='0'&&ch<='9')
    res=(res<<1)+(res<<3)+(ch^48);
    return res*f;
}
void add(int x,int y)
{
    e[++cnt].next=in[x];
    e[cnt].to=y;
    in[x]=cnt;
}
void add2(int x,int y)
{
    mp[++cnt2].next=in2[x];
    mp[cnt2].to=y;
    in2[x]=cnt2;
}
void tarjan(int u,int fa)
{
    int i,v;
    dfn[u]=low[u]=++seg;vis[u]=1;st[++top]=u;
    for(i=in[u];i;i=e[i].next)
    {
        v=e[i].to;
        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])
    {
        tot++;
        while(st[top+1]!=u)
        {
            col[st[top]]=tot;
            sz[tot]++;vis[st[top]]=0;
            top--;
        }
    }
}
int qpow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1)
        res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return res;
}
void deal(int u,int fa)
{
    int i,v;
    ed[u]>>=1;sum[u]=ed[u];
    for(i=in2[u];i;i=mp[i].next)
    {
        v=mp[i].to;
        if(v==fa)
        continue;
        deal(v,u);
        sum[u]+=sum[v]+1;
    }
}
void dfs(int u,int fa)
{
    int i,v;
    f[u][0]=qpow(2,ed[u]);
    f[u][1]=((qpow(2,ed[u]+sz[u])-f[u][0])%mod+mod)%mod;
    for(i=in2[u];i;i=mp[i].next)
    {
        v=mp[i].to;
        if(v==fa)
        continue;
        dfs(v,u);
        f[u][1]=(1ll*f[u][0]*f[v][1]%mod+1ll*(2ll*f[v][0]%mod+f[v][1])
        %mod*f[u][1]%mod)%mod;
        f[u][0]=2ll*f[u][0]%mod*f[v][0]%mod;
    }
    if(u==1)
    ans=(ans+f[1][1])%mod;
    else
    ans=(ans+1ll*f[u][1]*qpow(2,sum[1]-sum[u]-1)%mod)%mod;
}
int main()
{
    int i,j,x,y;
    n=read();m=read();
    for(i=1;i<=m;i++)
    {
        x=read();y=read();
        add(x,y);add(y,x);
    }
    tarjan(1,0);
    for(i=1;i<=n;i++)
        for(j=in[i];j;j=e[j].next)
        {
            x=e[j].to;
            if(col[i]==col[x])
            ed[col[i]]++;
            else
            add2(col[i],col[x]);
        }
    deal(1,0);dfs(1,0);
    printf("%d",ans);
    return 0;
}