LGP8867 [NOIP 2022] 建造军营 学习笔记
Luogu Link
题意简述
有一个 \(n\) 点 \(m\) 边的无向图。一种方案包含正整数个关键点与自然数条关键边，方案合法当且仅当去掉图中任何一条非关键边都不会导致任意两关键点不连通。问总方案数。
\(n\le 5\times 10^5\)，\(m\le 10^6\)，答案对 \(10^9+7\) 取模。保证无重边无自环。
做法解析
其实这道题里方案挺容易合法。因为要想一个方案不合法，就刚好需要一条非关键的割边两侧都有关键点，即“军营”。这意味着……？
你发现我们需要考虑原图的割边。所以我们先边双缩点一下。然后呢？
对于每个缩出来的点 \(u\)，我们令它原来包含的结点数为 \(v_u\)，边数为 \(e_u\)。则问题转化为：现在我们得到了一棵树。每个结点有 \(2^{e_u}\) 种不建军营的方案和 \(2^{v_u+e_u}-2^{e_u}\) 种建造军营（点题了）的方案，问有多少方案（不能不建）。
显然这时候就是个树形 \(\texttt{DP}\) 问题了。显然一个大点建不建会直接影响到转移，所以我们设出 \(f_{u,0/1}\) 表示当前大点 \(u\) 建或不建时 \(u\) 子树的总方案数。
思考转移。\(f_{u,1}\) 显然会对转移有更多的限制，所以我们先来考虑它。如果我们在 \(u\) 建了军营，接下来要么我们得保住 \(u\) 和父亲间的边，要么我们就放弃在 \(u\) 的子树外建任何军营。而 \(f_{u,0}\) 就不好限制住了，因为你不知道它下面有没有军营。这正启示我们：改设 \(f_{u,0/1}\) 为：\(u\) 子树内含有或不含有军营时的子树内总方案数。这就好办了，显然有：\(f_{u,0}=\prod 2f_{v,0}\)。
对于 \(f_{u,1}\)，如果我们如果想要在 \(u\) 外面继续建军营，就必须守住这条树边，反之则不用。因此我们在每个结点都结算一遍“外面没有军营（而且自己到父亲的边也没选）”的答案，然后强制选上树边转移，这样就可以不重不漏了（这段可以体会一下）。
另外别忘了还有种可能是 \(u\) 自己没有造军营，而是 \(u\) 的某个子树给它的，所以我们一边转移 \(f_{u,0}\) 的时候还有：\(f_{u,1}=\prod 2f_{v,0}+f_{v,1}\)，\(f_{u,1}\gets f_{u,0}\times f_{v,1}\)。没看懂的可以看代码。
代码实现
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
using namespace omodint;
using mint=m107;
const int MaxN=5e5+5;
int N,M,X,Y;
vector<int> Gr[MaxN];
void addudge(int u,int v){Gr[u].push_back(v);Gr[v].push_back(u);
}
int dfn[MaxN],low[MaxN],tot,stk[MaxN],ktp;
int bel[MaxN],bcnt;
void tarjan(int u,int f){dfn[u]=low[u]=++tot,stk[++ktp]=u;for(int v : Gr[u]){if(v==f)continue;if(!dfn[v])tarjan(v,u),minner(low[u],low[v]);else if(!bel[v])minner(low[u],dfn[v]);}if(low[u]==dfn[u]){bcnt++;int v;do{v=stk[ktp--],bel[v]=bcnt;}while(v!=u);}
}
vector<int> Tr[MaxN];
void addedge(int u,int v){Tr[u].push_back(v);}
int V[MaxN],E[MaxN],S[MaxN];
mint pw2[MaxN*3],F[MaxN][2],ans;
void DP(int u,int f){S[u]=E[u];for(int v : Tr[u]){if(v==f)continue;DP(v,u),S[u]+=S[v]+1;F[u][1]*=(F[v][0]*2+F[v][1]);F[u][1]+=F[u][0]*F[v][1];F[u][0]*=F[v][0]*2;}ans+=F[u][1]*pw2[M-S[u]-(u!=1)];
}
int main(){readis(N,M);pw2[0]=1;for(int i=1;i<=N+M;i++)pw2[i]=pw2[i-1]*2;for(int i=1;i<=M;i++)readis(X,Y),addudge(X,Y);tarjan(1,0);for(int u=1;u<=N;u++){V[bel[u]]++;for(int v : Gr[u]){if(bel[u]!=bel[v])addedge(bel[u],bel[v]);else E[bel[u]]++;}}for(int i=1;i<=bcnt;i++)E[i]>>=1,F[i][0]=pw2[E[i]],F[i][1]=pw2[V[i]+E[i]]-pw2[E[i]];DP(1,0);writi(miti(ans));return 0;
}
反思总结
作为一道树形 \(\texttt{DP}\)，其既包含“转移儿子前后缀‘累计’的东西”，又包含“如何不重不漏统计答案”这二者的技巧，是为好题。