【干啥啥不行枪毙正解第一名】NOIP2022 T3 建造军营（barrack） 题解

· · 题解

前言：目前（2022.12.7）题解区有一篇与笔者状态设计相同的题解，但那位神犇对于某个状态的计算好像有点繁琐（笔者个人认为），因此本题解大概不算重复解法，请各位至少看完状态转移方程导出部分，谢谢。

题意：给定一张无重边与自环的无向图，选出一个点集和一个边集（点集不得为空），定义一种选择方案是合法的当且仅当删除边集外任意一条边时点集中的所有点在原图中仍然联通，求总方案数对 {10}^9 +7 取模的结果。

看到“删除一条边后仍联通”之后非条件反射般想到边双缩点建边双树，至于为什么，大概是因为熟练吧，无向图中如果删掉一条边会对原图的子图的连通性造成影响，那条边一定是割边，而边双树的树边都是割边，并且树形结构具有很多优秀的性质。

发现定边之后选点比定点之后选边要麻烦很多（因为要保证合法性质），考虑讨论一个点的状态，之后对边决策。

发现边双点中的边选不选无所谓，因为随便割一条不会对连通性产生影响，它们都有两种选择，因此要决策的只剩下割边了。

给边双树钦定一个根（这里为一号结点），从子树角度考虑，设 f_u 为子树 u 中所有点的方案已经确定时的方案数（已确定部分点集不为空），g_u 为此时子树 u 外的方案数，这个点的贡献 h_u=f_u\times g_u。设边双树上子树 u 的大小为 ts_u，由乘法原理后者为 2^{ts_1-ts_u-1}，其中 ts_1-ts_u 是边双树子树 u 之外的边数，再减一是因为 u 到 fa_u 的连边此时强制不选，否则会造成重复，原因在于规定点集不为空，若选择了这条边，这种方案会在 f_{fa_u} 中包含，造成重复计数。

对于 f_u 的计算，因为是对于子树的相关计算，可以按照树形结构作为阶段决策每一条边，考虑计数动态规划。其实笔者当时根本没想这么多，这种东西百分之八九十都是 DP ，经验问题吧，大概。

继续讨论结点状态，发现 f_u 可以从自己不选的儿子进行转移，因此再开一维存不选自己时的状态数，但不选自己时可能子树内有被选择的点，针对这种情况直接简单粗暴地再开一维。

令 dp_{u,0/1/2} 表示子树 u 内当结点 u 的状态为被选择（0）/未被选择但子树中有点被选择（1）/一个点也没选（2）时的方案数，考虑转移。

对于 dp_{u,0}，为了保证方案合法，其必须有连边，因此它作为前驱状态时边的选择方案数为 1（必选），而它可以从任意状态的点转移。

对于 dp_{u,1}，按照它的定义它作为前继时也必须被连边，而同样可以从任意状态转移，只不过需要一点小小的特殊处理，详见下文。

对于 dp_{u,2}，根据定义它只能从与它类型相同的状态转移，否则会与 dp_{u,1} 发生重复计数。由于没有对于方案合法性的要求，关于它的连边可选可不选，方案数为 2。

这时候拿样例 1（没错就是那个只有两个点一条边的样例 1）试一下会发现 dp_{u,1} 算重了，其原因在于按照 dp_{u,0} 的转移方式进行转移时会算入选择的边都连到 dp_{x,2} 也就是最后一种情况的点上，与 dp_{u,1} 的定义相悖，需要把不合法的方案减掉。

容易发现这个不合法部分我们已经定义过了，就是 dp_{u,2}，因此在处理完结点 u 的转移之后将 dp_{u,1} 减去 dp_{u,2} 即可。

至于初始状态，dp_{u,0} 是选择该边双联通分量点，设 es_{u} 为边双联通分量点 u 中的点数，则它初始的方案数为 2^{es_{u}} -1，前一部分由乘法原理（每个点可选可不选），后面减一减掉的是一个点都不选的方案，否则与定义相悖。dp_{u,1} 与 dp_{u,2} 的初始方案数都只有不选，均为 1。细心的读者可能会提出疑问：如果 u 是叶子，dp_{u,1} 不该为 0 吗？确实是这样，但是程序实现中直接减去 dp_{u,2} 后就是 0 了，至于为什么可以自己思考一下，挺有意思的。

综上，转移方程为：

dp_{u,0}=dp_{u,0}\times \prod_{v\in son(u)}(dp_{v,0}+dp_{v,1}+2\times dp_{v,2}) dp_{u,1}=dp_{u,1}\times \prod_{v\in son(u)}(dp_{v,0}+dp_{v,1}+2\times dp_{v,2}) dp_{u,2}=dp_{u,2}\times \prod_{v\in son(u)}(2\times dp_{v,2}) dp_{u,1}=dp_{u,1}-dp_{u,2}

按照定义，f_{u}=dp_{u,0}+dp_{u,1}，那么设答案为 ans，有

ans=2^{m-(ts_1 -1)} \times \sum f_u \times g_u

其中 2^{m-(ts_1 -1)} 为全部边双联通分量中的边的贡献，m-(ts_1 -1) 为边双联通分量中的边数，m 同题意，ts_1 -1 为边双树的边数。

预处理模数意义下 2 的若干次幂后可以线性转移，时间复杂度 \Theta(n)。

注意取模，以及 Tarjan 算法求边双联通分量的实现，笔者就是因为这里写炸挂了 20 分。

官方数据也 A 了。

code：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+10,p=1e9+7;
struct edge
{
    int to,nxt;
}T[N*2];int cnt2,H2[N];
int n,m;
vector<int> G[N];
inline void add_Edge(int u,int v)
{
    G[u].emplace_back(v);
}
inline void add_T(int u,int v)
{
    T[++cnt2]=edge{v,H2[u]};H2[u]=cnt2;
}
#define RAPE(x) for(auto v:G[x])
#define Rape(x) for(int i=H2[x];i;i=T[i].nxt)
int dp[N][3],p2[N*3+1];
//dp[u][0]=dp[u][0]*dp[v][0]+dp[u][0]*dp[v][1]+dp[u][0]*2*dp[v][2]
//dp[u][1]=dp[u][1]*dp[v][0]+dp[u][1]*dp[v][1]+dp[u][1]*2*dp[v][2]
//dp[u][2]=dp[u][2]*2*dp[v][2]
//dp[u][1]-=dp[u][2]
int stk[N],top;
int ebcsz[N],ebcc,ebc[N],dfc,dfn[N],low[N];
int tarjan(int u,int f)
{
    low[u]=dfn[u]=++dfc;stk[++top]=u;
    RAPE(u) if(v^f)
    {
        if(!dfn[v]) low[u]=min(low[u],tarjan(v,u));
        else low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        ++ebcc;int x;
        do
        {
            x=stk[top--];
            ebc[x]=ebcc,++ebcsz[ebcc];
        }while(x^u);
    }
    return low[u];
}
int ts[N];
inline int add(int x,int y) {return (1ll*x+y>=p)?x-p+y:x+y;}
inline int sb(int x,int y) {return add(x,p-y);}
inline int kake(int x,int y) {return 1ll*x*y%p;}
int treedp(int u,int f)
{
    dp[u][0]=sb(p2[ebcsz[u]],1);dp[u][1]=dp[u][2]=ts[u]=1;
    Rape(u) if(T[i].to^f)
    {
        int v=T[i].to;ts[u]+=treedp(v,u);
        dp[u][0]=add(add(kake(dp[u][0],dp[v][0]),kake(dp[u][0],dp[v][1])),kake(kake(2,dp[u][0]),dp[v][2]));
        dp[u][1]=add(add(kake(dp[u][1],dp[v][0]),kake(dp[u][1],dp[v][1])),kake(kake(2,dp[u][1]),dp[v][2]));
        dp[u][2]=kake(kake(2,dp[u][2]),dp[v][2]);
    }
    dp[u][1]=sb(dp[u][1],dp[u][2]);
    return ts[u];
}
int u,v,ans;
int main()
{
    freopen("barrack.in","r",stdin);
    freopen("barrack.out","w",stdout);
    ios::sync_with_stdio(0);
    cin>>n>>m;p2[0]=1;
    for(int i=1;i<=m*2;++i) p2[i]=kake(p2[i-1],2);//,cout<<p2[i]<<" ";cout<<endl;
    for(int i=1;i<=m;++i) cin>>u>>v,add_Edge(u,v),add_Edge(v,u);
    tarjan(1,0);//for(int i=1;i<=ebcc;++i) cout<<ebcsz[i]<<endl;
    for(u=1;u<=n;++u) RAPE(u) if(ebc[v]^ebc[u]) add_T(ebc[u],ebc[v]);
    treedp(1,0);//for(int i=1;i<=ebcc;++i) cout<<dp[i][0]+dp[i][1]<<endl;
    for(int i=1;i<=ebcc;++i) ans=(1ll*ans+1ll*((dp[i][0]+dp[i][1])%p)*p2[max(0,ts[1]-ts[i]-1)]%p)%p;
    ans=1ll*ans*p2[m-ts[1]+1]%p;
    cout<<ans;
    return 0;
}

后记：

按照上面的状态设计，在不关闭流同步时因常数问题可能在某些 OJ 会被卡掉 5-15pts。

实际上，上面的 f_u 可以在上面思路的基础上直接DP计算，在转移时只需要一个额外变量辅助转移即可，可以极大优化运行效率，虽然没太大必要。

转移方程其实差不太多，留给读者思考。

改过之后的 Code 在此。