本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-15 22:57:56

对于 $n \le 16,m \le 25$ 和性质 A。

这 45 分是白送。

100pts

要保护的是割边，所以考虑边双缩点。

显然，缩点之后一定是一棵树，每个点（或者说是边双连通分量）内部的边不需要保护。

考虑树形 dp。
设 $dp_{i,1/0}$ 为以节点 $i$ 为根的子树建造军营和不建造军营的方案数。

但是发现对于 $i$ 不建造军营，子树建造军营的部分，无法确定 $i$ 到子树的边选不选，因为我们不知道 $i$ 为根的子树以外是否有军营。

只能增加限制。

具体地说，状态增加一条，强制 $i$ 子树内选的点能通过选的边和 $i$ 连通。

然后树形 dp 求出所有的 $dp_{i,1/0}$，这一部分比较容易。

大概写一下自认为比较难的部分的流水账：
统计答案，我们对于每个 $i$，假定所有的军营都在以 $i$ 为根的子树内，并且与 $i$ 相连，既然与 $i$ 相连，那么为了不让答案算重，就不能选 $father_i$ 到 $i$ 的边。

式子也就能推出来了。

结束。

#include <bits\/stdc++.h>
using namespace std;
const int maxn=5e5+5;
const int maxm=1e6+5;
typedef long long ll;
const ll MOD=1e9+7;
int n,m;
int head[maxn];
struct EDGE
{
    int to,nxt;
}edge[maxm<<1];
int cnt=1;
void add(int u,int to)
{
    edge[++cnt].to=to;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
vector<int> G[maxn];
int dfn[maxn],low[maxn],dfcnt;
bool ins[maxn];
bool cut[maxm<<1];
int bccnt;
int e[maxn],v[maxn];
int color[maxn];
void tarjan(int u,int _fa)
{
    dfn[u]=low[u]=++dfcnt;
    ins[u]=1;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(to==_fa)continue;
        if(!dfn[to])
        {
            tarjan(to,u);
            low[u]=min(low[u],low[to]);
        }
        else
        {
            low[u]=min(low[u],dfn[to]);
        }
        if(low[to]>dfn[u])cut[i]=cut[i^1]=1;
    }
    ins[u]=0;
}
bool visnode[maxn];
void dfs(int u)
{
    visnode[u]=1;
    v[bccnt]++;
    color[u]=bccnt;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(!visnode[to]&&!cut[i])
        {
            dfs(to);
        }
    }
}
int sub_edgecnt[maxn];
ll pw[maxn+maxm*2];
ll f[maxn][2];
ll ans=0;
void calcsub(int u,int _fa)
{
    sub_edgecnt[u]=e[u];
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(to==_fa)continue;
        calcsub(to,u);
        sub_edgecnt[u]+=sub_edgecnt[to]+1;
    }
}
void dp(int u,int _fa)
{
    f[u][0]=pw[e[u]];
    f[u][1]=(pw[v[u]+e[u]]-pw[e[u]])%MOD+MOD;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(v==_fa)continue;
        dp(v,u);
        f[u][1]=f[u][0]*f[v][1]%MOD+f[u][1]*(2ll*f[v][0]+f[v][1])%MOD;
        f[u][1]%=MOD;
        f[u][0]=f[u][0]*2ll*f[v][0]%MOD;
    }
    ans+=f[u][1]*pw[sub_edgecnt[1]-sub_edgecnt[u]-(u!=1)]%MOD;
    ans=(ans%MOD+MOD)%MOD;
}
int main()
{
    scanf("%d%d",&n,&m);
    pw[0]=1ll;
    for(int i=1;i<=n+m;i++)
    {
        pw[i]=pw[i-1]*2ll%MOD;
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].emplace_back(v);
        G[v].emplace_back(u);
        add(u,v);
        add(v,u);
    }
    tarjan(1,0);
    for(int i=1;i<=n;i++)
    {
        if(!visnode[i])
        {
            ++bccnt;
            dfs(i);
        }
    }
    memset(head,0,sizeof head);
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int to:G[i])
        {
            if(color[i]!=color[to])
            {
                add(color[i],color[to]);
            }
            else
            {
                e[color[i]]++;
            }
        }
    }
    for(int i=1;i<=bccnt;i++)
    {
        e[i]\/=2;
    }
    calcsub(1,0);
    dp(1,0);
    printf("%lld",ans);
    return 0;
}