题解 P3687 【[ZJOI2017]仙人掌】

· · 题解

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

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{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] 种匹配中，

然而，

\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