[AGC067E] Biconnected Graph

· · 题解

分享一下自己对这个 DP 的理解，可能是错的，欢迎指出！

[AGC067E] Biconnected Graph

题意

给定 n，计算 n 个点的边双的数量（允许重边，不允许自环），满足这个边双删除任意一条边后都不是边双，输出答案对 P 取模的结果。

### 分析 我们先尝试删掉任意一条边，观察图的性质：由于我们要求删边后不是边双，所以现在的图缩点后一定是一个树形结构；我们又要求把边加回去后，图会变回一个孤立边双，所以现在的图一定是一条链。也就是说，如果把删掉的边加回去，缩点后会形成**一个环**。我们称这个环为这条边的**生成环**，将环边的端点成为**关键点**，显然每个边双分量又一/两个关键点。 我们注意到，我们已经找到了一个递归到子问题的结构：即将一个边双拆分为一个环（环上的每个边双分量都满足题目条件）。然而一点不同是，我们发现每个边双分量的两个关键点存在一条从**外部的环边**连通的路径；继续递归下去，我们可能会在一个边双分量中添加若干条外部的附加边。于是考虑设计状态：$dp(n, k)$ 表示 $n$ 个点，节点 $1, \dots, k$ 可以通过外部的边连通，的边双数量（钦定是 $1, \dots, k$ 最后在将编号乘回来），记这 $k$ 个节点为**特殊点**。 那么转移就是考虑枚举一条边，然后顺着生成环 DP。为了不算重，我们考虑钦定这条边的端点之一是 $1$ 号节点。那么就可以断环成链，最好在包含 $1$ 号节点的边双将链连接起来就可以了。注意到这样 DP 的话，对于 $1$ 号节点的每一条出边，都会计算一遍同一张图，所以我们应将 $deg_1$ 记录进状态中，最后在将方案数除以 $deg_1$。 接下来详细叙述一下转移方程。 其主要逻辑是：将小的边双合并起来，可以钦定其中一些点和 $1$ 相连，直接背包。然而每次枚举的生成环对于子边双而言都会产生一些新的附加边，也就是说，对于子边双而言，一些特殊点的**附加边变为了内部边**，于是相映的将这些点去除。注意：一对点直接可以存在多条外部边。 我们同样需要观察，由于连接了外部边，会对这个边双的结构产生哪些限制：具体而言，我们发现特殊点所在的边双**在环上不能相邻**，注意两个点可以同时在一个边双。所以在环上 DP 的过程中，我们需要记一维 $0/1$ 表示环上的上一个子边双是否存在特殊点。 记 $dp'(n, k, d)$ 表示 $n$ 个点，$1, \dots, k$ 为特殊点，$deg_1 = d$ 的方案数；$dq(n, k, 0/1)$ 表示 $n$ 个点，钦定其中的 $k$ 个将成为大边双的特殊点，上一个子边双是否含特殊点的方案数。 具体转移如下： - 考虑连接链成环，我们钦定其中一个关键点一定是 $1$，只用决策另一个关键点，显然这个关键点也一定是特殊点，并且一定会在 $1$ 和这个特殊点之间产生一条外部边。记 $X = dq(n_1, k_1, 0) \times \dbinom{n - k}{n_1 - k_1} \times \dbinom{k - 1}{k_1}$，以下转移均贡献到 $dp'(n, k, d)$： - 钦定这条外部边不是连接两者的最后一条：$X \times (k_2 - 1) \times dp'(n_2, k_2, d - 1)$； - 钦定这条外部边是连接两者的最后一条，同时考虑上这个特殊点的编号：$X \times (n_2 - k_2) \times dp'(n_2, k_2 + 1, d - 1)$； - 钦定关键点只有一个：$X \times dp'(n_2, k_2, d - 2)$； - 二元环，且两者都只有一个关键点，要求 $k_1 = 0$：$dp(n_1, 1) \times n_1 \times \dbinom{n - k}{n_1} \times dp'(n_2, k_2, d - 2)$。 - 链上的转移，初值 $dq(0, 0, 1) = 1$，转移中 $dq(*, *, 0/1) \times dp(*, 0) \to dq(*, *, 0)$，$dq(*, *, 0) \times dp(*, k) \to dq(*, *, 1)$（$k > 0$），记 $X = dq(n_1, k_1, *) \times \dbinom{n - k}{n_1 - k_1} \times \dbinom{k}{k_1}$，具体的系数： - 钦定不变：$X \times k_2 \times k_2 \times dp(n_2, k_2)$； - 钦定是最后一条边，注意有正反两种连法：$X \times 2 \times k_2 \times (n_2 - k_2) \times dp(n_2, k_2 + 1)$； - 一类特殊的情况是，注意到，我们的定义是在外部相连，那么和 $1$ 不属于同一边双的关键点显然和 $1$ 是相连的，那么如果我钦定剩余的点未来也要和 $1$ 相连，那么这一对/一个关键点显然也是和剩下部分相连的，也就是说满足定义！ - 一个关键点：$X \times (n_2 - k_2) \times dp(n_2, k_2 + 1)$； - 一对关键点：$X \times (n_2 - k_2) \times (n_2 - k_2 - 1) \times dp(n_2, k_2 + 2)$。 注意边界情况，详见代码，以上。 ### Code 提交记录：<https://atcoder.jp/contests/agc067/submissions/59260276>。