自动搬运

查看原文

来自洛谷，原作者为

	brealid @Pride205 你是xnn

搬运于2025-08-24 21:51:36，当前版本为作者最后更新于2020-06-03 09:02:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

整个算法范围两部分：判断仙人掌与得出答案

Part 1 判断仙人掌

对于一个无自环无重边的无向连通图，方案数非 $0$ 当且仅当这个图本身满足仙人掌的性质（即：任意一条边最多属于一个简单环）。

因此我们需要判断仙人掌。

注意这道题的特殊性，你会发现，一个简单环对答案是无贡献的（原因请看 Part 2）。

因此我们不需要存储每个环包括多少条边，以及包含的边是什么。我们只需要对处于简单环中的边打上删除标记即可。

因此，在仙人掌判断中，
$\color{red}\texttt{你不需要 tarjan, 或者树上差分，你只需要暴力}$
解释 在 dfs 中，当你发现这条边指向的节点不是父亲，但却已经被访问过，设这条边为 $u-v$，那么 $u-v-LCA(u,v)-u$ 构成一个环，你只需要用类似暴力求LCA的方法一层层往上爬，并对爬到的边打标记即可。不要忘了给 $u-v$ 打上删除标记。

正确性 一条边至多只可能被打一次的删除标记。如果被打第二次，那么可以判断这条边至少处于两个简单环中，因此立即返回并输出 $0$（无解）。

注意，
$\color{red}\texttt{1. 你最好需要邻接表存图。}$
解释 因为若你对一条边 u-v 打标记，你肯定也要对 v-u 打标记。使用编号从 $0$ 开始的邻接表时，如果要对编号为 $e$ 的边打标记，对 $\lfloor\frac{e}{2}\rfloor$ 打标记即可。使用 $vector$ 存图会麻烦很多。
$\color{red}\texttt{2. 你最好需要存，从父亲节点到自己的边的编号。}$
解释 因为在暴力对一个环上的边打标记时，存下这条“到父边”（姑且让我用这个名词吧）可以保证跳到父亲的复杂度为 $\Theta(1)$ 的。不存这条边，只能暴力搜索出边，均摊复杂度 $\Theta(\frac{m}{n})$。（当然，你要跟我说最好情况都是 $\Omega(1)$，我也没办法。但是出题人大概率不会这么良心。）
$\color{red}\texttt{3. 一旦发现当前图不是仙人掌，立即返回。}$
解释 如果等到搜索结束再返回，复杂度可以被卡到最坏 $O(n^2)$。

Part 2 求解仙人掌

现在我们已经确定原图为仙人掌（非仙人掌右转 puts("0")），并且对环上的边打上了删除标记。

$\color{blue}\texttt{Q:}$ 为什么“环上的边对答案无贡献”？
$\color{blue}\texttt{A:}$ 显然，环上的边已经处于一个简单环之中。因此根据仙人掌的定义，我们不能把这些“环上的边”包含到其他简单环之中。因此这些边不可能对答案有贡献。

引理 考虑到原图已经被我们划分成了一些树，而且这些树之间是不会互相影响的。
证明 注意到，如果你想对两棵树上的两个节点连边，由于原图是无向连通图，因此这两棵树原来肯定被一条环上的链所连接。因此，若要对这两棵树上的这两个节点连边，原来环上的链就会被覆盖 $2$ 次，不符合仙人掌定义。

因此，我们可以对每棵树单独求解，然后将答案利用乘法原理乘起来即可。

---

考虑现在我们达到了什么。
我们成功将一道 仙人掌 上的问题转化成了 树 上的问题（部分分 #6~#7）

---

考虑设计 $DP$。

先把辅助数组 $h$ 讲了。
$h[i]$ 表示有 $i$ 个点，它们之间匹配的方案数
简单来讲，现在有 $i$ 个点，都是某个节点 $u$ 的孩子，而且这 $i$ 个节点各自到 $u$ 的边都没有被简单环覆盖（易知：$i=\operatorname{size_{Children_u}}$）
考虑到如果连一条边 $v-w$ 那么 $v-u$ 与 $w-u$ 这两条边都会被覆盖。
故：一个点 $v$ 最多只能与它的兄弟连一条边。

由于 $h$ 值与树的形态无关，可以预处理。
假设已有 $i - 1$ 个点，现在加入 $1$ 个点。
这个点可以不与任何兄弟连边，方案数为 $h[i - 1]$
这个点可以选择与一个兄弟连边，有 $i - 1$ 种选择，每种选择带来 $h[i - 2]$ 的贡献，方案数 $(i - 1)·h[i - 2]$

所以，

$$h[i] = h[i - 1] + (i - 1)·h[i - 2]$$

$\color{red}\texttt{这时候你要想清楚这个状态为什么设计。}$

设计状态 $g[u]$ 表示节点 $u$ 可向上拓展 的方案数。

考虑 $g[u]$ 的转移。
由 $g[u]$ 的意义，我们需要在 $u\cup\operatorname{Children_u}$ 中选出一个节点，作为接口节点，可以同父亲的其他直接孩子的子树节点连接。
因为 $u-fa[u]$ 这条边最多只能属于一个简单环，所以保留一个接口节点即可。

我们有

$$g[u] = h[Deg + 1] · \prod_{v\in \operatorname{Children_u} }g[v] $$

其中 $Deg$ 表示 $\operatorname{size_{Children_u}}$

注意到，此时我们将节点 $u$ 自身也作为 $\operatorname{Children_u}$ 的一个兄弟来计算。关于这点，理解方式有二：

1. $g[u] = h[Deg] · \prod_{v\in \operatorname{Children_u} }g[v] + Deg · h[Deg - 1] · \prod_{v\in \operatorname{Children_u} }g[v]=\texttt{原式}$
   如果把 $u$ 自身作为接口节点，方案数为加号左边，不解释；
   如果把 $u$ 的一个孩子作为接口节点，方案数为加号右边。
   • 解释：选择一个孩子（$Deg$）剩下的任意匹配（$h[Deg - 1]$）再乘上孩子的 $g$ 值（$\prod_{v\in \operatorname{Children_u} }g[v]$）
2. 如果在 $h[Deg + 1]$ 种匹配中，
   • $u$ 被连边：假设 $u-v$ 被连，那么这条边的意义不是连接，而是选定 $v$ 作为接口节点
   • $u$ 未被连边：$u$ 即接口节点

然而， $\color{red}\texttt{答案不是 g[root]}$

考虑到在 $g$ 的转移中，有可能 $u-v$ 被连 $(v\in \operatorname{Children_u})$。这时，按照我们的理解，$v$ 被选中作为接口节点。
但是 $root$ 节点不再向上延伸，$root$ 节点不需要接口节点，接口节点的存在只会导致答案重复统计
在 $g$ 的转移中，我们确实重复统计了一些边的贡献，但是这“重复统计”的前提是“接口节点”
意即：$g[u]$ 被 $fa[u]$ 所统计，才是“重复统计”的正确性之源。

$\color{red}\texttt{对于一棵树，答案是 }h[Deg_{root}] · \prod_{v\in \operatorname{Children_{root}} }g[v]$

这样不会重复统计。
这也就是其他很多题解中提到的 $f$ 数组。

代码

见 gitee 仓库 https://gitee.com/hkxa/mycode/blob/master/luogu/P3687.cpp