洛谷P8867 [NOIP2022] 建造军营

之前 NOIP 的时候还没学 Tarjan 算法，无奈爆零，现在学完了，终于花一个下午自己做出来了。

前置知识：

题目做法

首先，会想到边双连通分量缩点，因为在非桥边上无论保护还是不保护都是一样的。

在缩点之后，一定会形成一棵树（因为存在环就还存在边双连通分量）。在树上考虑进行树形 DP 进行计数。

我们定义 fu,0\large{f_{u,0}} 为 uu 所在的边双连通分量没有建造军营的方案数。fu,1\large{f_{u,1}} 为 uu 所在的边双连通分量建造了军营的方案数。并且若 uu 建造了军营，uu 到根节点的边必须全部保护（这么设计是为了方便转移状态，但是统计答案时就不是 froot,1\large{f_{\text{root},1}} 了）。

定义如下变量：

  • edgeuedge_u：uu 所在连通分量的边数；
  • vertexuvertex_u：uu 所在连通分量的点数；
  • sizusiz_u：uu 的儿子数。

并定义 v∈uv \in u 代表 vv 是 uu 的儿子。

则可以写出边界条件：

fu,0=2edgeu\large{f_{u,0}=2^{edge_u}}

   若叶子节点不建军营，方案数就是 2edgeu2^{edge_u}，因为每条非桥边都可以随便保护或不保护。

fu,1=2edgeu(2vertexu−1)\large{f_{u,1}=2^{edge_u}\left(2^{vertex_u}-1\right)}

   若叶子节点建了军营，有 (2vertexu−1)\left(2^{vertex_u}-1\right) 种建造方案，根据乘法原理可知，方案数为 2edgeu(2vertexu−1)2^{edge_u}\left(2^{vertex_u}-1\right)。


以及转移条件：

fu,0=2edgeu+sizu∏v∈ufv,0\large{f_{u,0}=2^{edge_u+siz_u}\prod_{v\in u}{f_{v,0}}}

   若节点 uu 的子树不建军营，所有的儿子都不能建军营，内部的道路随便保护或不保护，以及和儿子的连边随便保护或者不保护，共有 2edgeu+sizu2^{edge_u+siz_u} 种方案，再乘上所有子节点的 fv,0f_{v,0} 即可。

fu,1=2edgeu+vertexu∏v∈u(2fv,0+fv,1)−fu,0\large{f_{u,1}=2^{edge_u+vertex_u}\prod_{v\in u}\left({2f_{v,0}+f_{v,1}}\right)-f_{u,0}}

   若节点 uu 的儿子建立了军营，则这条边必须保护（上文加粗的特殊条件），否则这条边保护或者不保护，根据加法原理可知，有 (2fv,0+fv,1)\left({2f_{v,0}+f_{v,1}}\right) 种方案。uu 内部也可以建军营，有 2vertexu2^{vertex_u} 种方案，最后乘上内部的边随便保护或者不保护的 2edgeu2^{edge_u} 种方案。但是这样多统计了一个军营都没有造的情况，减去 fu,0f_{u,0} 即可的得到答案。


接下来就是统计答案。我们知道，在统计时，我们规定了若 uu 建造了军营，uu 到根节点的边必须全部保护。但是事实上在 uu 建造军营后，如果不在 uu 的子树中的节点全部不建造军营，则其他的边可以随便保护不保护。可以发现，这种情况正好就是 2cnt_left_edgefu,1\large{2^{\text{cnt\_left\_edge}} f_{u,1}}。其中 cnt_left_edge\text{cnt\_left\_edge} 代表不在 uu 的子树中的边数，特别的，我们不能统计 uu 和其父亲的连边（因为若保护了父亲的连边，会与之前统计过的情况重复）。用一次 DFS 求出节点子树内的边数 subtree_edgesubtree\_edge，在用总边数 mm 进行修改即可。即：

cnt_left_edgeu={m−subtree_edgeu,u为根节点m−subtree_edgeu−1,u不是根节点\text{cnt\_left\_edge}_u=\left\{ \begin{aligned} &m-subtree\_edge_u &,u\text{为根节点}\\ &m-subtree\_edge_u-1&,u\text{不是根节点}\\ \end{aligned} \right.

最后答案即为

∑2cnt_left_edgefi,1\large{\sum{2^{\text{cnt\_left\_edge}}f_{i,1}}}

最后，如果你代码写完后，发现跑样例4报段错误了，是你栈空间只有 8M 爆栈了，直接 ulimit -s unlimited 就可以了。

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const ll M = 1e9+7;

ll fast_pow(ll a,ll b){
    ll res = 1;
    while(b>0){
        if(b&1)res=(res*a)%M;;
        a=(a*a)%M;
        b>>=1;
    }
    return res;
}

const int N = 6e5+5;

int n,m;
struct Edge{
    int u,v;bool flag;
};
vector<Edge> edges;
vector<int> G[N];

int dfn[N],low[N],dfs_clock;

void tarjan(int u,int fa){
    dfn[u]=low[u]=++dfs_clock;
    for(int eid:G[u]){
        int v = edges[eid].v;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);

            if(low[v]>low[u]){
                edges[eid].flag=1;
                edges[eid^1].flag=1;
            }
        }
        else if(v!=fa){
            low[u]=min(low[u],dfn[v]);
        }
    }
}

int vertex_cnt[N],edge_cnt[N];
int fa[N];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int i,int j){
    fa[find(i)]=find(j);
}
vector<int> G2[N];

ll dp[N][2];
ll ans = 0;

ll subtree_edge[N];

void pre(int u,int father){
    subtree_edge[u]=edge_cnt[u];
    for(int v:G2[u]){
        if(v==father)continue;
        pre(v,u);
        subtree_edge[u]+=subtree_edge[v]+1;
    }
}

void dfs(int u,int fand){
    bool flag=0;
    for(int v:G2[u]){
        if(v==fand)continue;
        flag=1;
        dfs(v,u);
    }
    
    // 是叶子节点
    if(!flag){
        dp[u][0]=fast_pow(2,edge_cnt[u]);
        dp[u][1]=(fast_pow(2,vertex_cnt[u]))*(dp[u][0])%M;
    }
    else{
        if(u==fand)
            dp[u][0] = fast_pow(2,edge_cnt[u]+G2[u].size());
        else
            dp[u][0] = fast_pow(2,edge_cnt[u]+G2[u].size()-1);

        
        dp[u][1] = fast_pow(2,vertex_cnt[u]+edge_cnt[u]);
        for(int v:G2[u]){
            if(v==fand)continue;
            dp[u][0] = dp[u][0]*dp[v][0]%M;
            dp[u][1] = dp[u][1]*(2*dp[v][0]+dp[v][1])%M;
        }

    }

    dp[u][1] = (M+dp[u][1]-dp[u][0])%M;
    
    ans = (ans + dp[u][1]*fast_pow(2,m-subtree_edge[u]-1)%M)%M;
}


int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        edges.push_back({u,v,0});
        edges.push_back({v,u,0});
        int cnt = edges.size();
        G[u].push_back(cnt-2);
        G[v].push_back(cnt-1);
    }

    // 因为图是连通的，只需要进行一次dfs
    tarjan(1,1);

    // 建立新图
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(auto e:edges){
        if(e.flag)continue;
        merge(e.u,e.v);
    }
    for(auto e:edges){
        int u=find(e.u),v=find(e.v);
        if(u==v){
            edge_cnt[u]++;
        }
        else{
            G2[u].push_back(v);
        }
    }

    for(int i=1;i<=n;i++){
        edge_cnt[i]/=2;
        vertex_cnt[find(i)]++;
    }

    pre(fa[1],fa[1]);
    dfs(fa[1],fa[1]);    

    printf("%lld\n",ans);

    return 0;
}