自动搬运

查看原文

来自洛谷，原作者为

	251Sec 祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。

搬运于2025-08-24 23:09:07，当前版本为作者最后更新于2025-01-31 22:21:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题意简述

对 $n$ 个点的无向连通图或树计数，要求存在恰好一种方案把它的点集划分成若干连通块，每个连通块直径不超过 $2$。对输入的模数 $P$ 取模。

$1 \le n,T \le 5 \times 10^3$，$0 \le t \le 1$，$1 \le P \le 1.05 \times 10^9$。

解法

特判 $n \le 3$ 的情况，我们接下来的讨论可能在这些边界上出错。

第一个观察是，对于任何 $n \ge 2$ 的连通图，存在至少一种划分方案。

显然只需要对树证明，我们直接给出构造。首先一个树上的合法点集形如一个菊花。按照一个你喜欢的顺序加入每个点 $u$，考虑和它相邻的点 $v$。

若 $v$ 未被加入任何菊花，直接把 $u,v$ 配对。

若 $v$ 是一个菊花的中心，直接把 $u$ 加入 $v$ 的菊花。

否则，若 $v$ 所在菊花大小大于 $2$，可以把 $v$ 从那个菊花里拿出来和 $u$ 配对。

否则，$v$ 所在菊花大小等于 $2$，可以直接把 $v$ 作为那个菊花的中心，把 $u$ 加入。

这样就构造出了一组方案。

实际上这给出了一个信息：考虑两组把原图划分成若干大小 $\ge 2$ 的连通块的方案和一个点 $u$，令 $u$ 在两组方案里所在连通块的点集为 $S,T$，若 $S \cap T = \{u\}$，则它们一定给出了两种不同的最终构造方案。

接下来考虑树的情况。我们给出如下结论：对于一棵树，满足条件当且仅当所有非叶节点和至少一个叶子相邻。其中叶子指度数为 $1$ 的点，后面讨论一般图时，我们也这么定义叶子。

必要性：如果有一个点不和任何叶子相邻，那么删去它可以得到至少两个大小 $\ge 2$ 的连通块，设它们为 $A,B$，那么 $\{A,B\cup\{u\}\}$ 和 $\{B,A\cup\{u\}\}$ 给出了两种不同的划分。

充分性：考虑归纳，我们每次找到任意一个非叶节点 $u$，考虑所有和它相邻的点 $v$，如果 $v$ 是叶子，那么 $v$ 必须和 $u$ 划分到一起，否则 $v$ 必定不能和 $u$ 划分到一起。（因为这样做会产生孤立的大小为 $1$ 的连通块）删去 $u$ 和所有与 $u$ 相邻的叶子之后递归到一个子问题。

对于一般图的情况我们有类似的结论：对于一个 $n \ge 4$ 的无向连通图，满足条件当且仅当对所有非叶子节点 $u$，它都和至少一个叶子相邻。

为了证明它，我们先给出一个引理：对于 $n \ge 4$ 的合法的无向连通图，不存在一个非叶节点，删去后原图仍然连通。

考虑反证，最坏情况是：删去这个点之后剩下一棵树且删去的节点度数为 $2$，我们只需证明这种情况下有至少两种方案。提取出和删去节点相邻的两个点之间的树上路径，和这两条边组成一个环，则我们图的形态形如一个环往外挂一些连通块。

如果环上某个点往外挂的所有连通块都有 $\ge 2$ 个点，那么这个点加入与不加入某个连通块就有两种方案。否则删去所有往外挂的 $\ge 2$ 个点的连通块，一定可以得到一个 $\ge 4$ 的纯环或者一个环往外挂叶子的形式，且一定有至少一个点没往外挂叶子。（对应那个度数为 $2$ 的点）不难验证这些情况下都有至少两种方案。

于是现在每个点要么是叶子要么删去后可以得到至少两个连通块。仿照树的情况，我们可以证明原结论。

接下来只需要考虑如何计数。枚举非叶节点的个数，则它们应当组成一个连通图或一棵树，且每个点上要挂至少一个叶子，令 $f_i$ 代表 $i$ 个点的连通图或树的个数，答案为：

$$\sum_{i=1}^n f_i \begin{Bmatrix}n-i \\ i\end{Bmatrix}\binom{n}{i}i! $$

容易在 $O(n^2)$ 复杂度内预处理后 $O(n)$ 回答单组数据。

据说存在 NTT 模数下 $O(n \log^2 n)$ 复杂度的做法，有没有大神来搞一下。