——琉璃，你能向神发誓吗？

· · 题解

题意简述

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

### 解法 特判 $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)$ 复杂度的做法，有没有大神来搞一下。