CF641G Little Artem and Graph 题解（DP ver.）

出题人以为自己出了神仙 dp 题然后被矩阵树定理杀穿了。提交记录全是矩阵树定理做法。无敌了。

为了体谅出题人，本篇题解来说说 dp 做法（绝对不是因为我不会矩阵树定理！）。

感觉是被低估的题目啊。

下文所说的 均指原题的 ，也就是每次加入点后，新加入的点和原先的连边的点形成的团的大小。

首先需要考虑树的性质。树的性质是有 条边的联通的无环的图。

你发现肯定是要对某种满足条件的加边序列进行计数，因为你很难直接维护树的结构。

考虑如何去重，我们分批次加边，每条边在两个端点中标号较大的点加入，将每个点加入的边集记录下来作为生成树的代表元。容易发现这样的方案唯一对应了一颗生成树。

例如这张图可以在每个节点加入这些边得到一颗生成树：

仔细观察这张图，发现每次加点都会构成一个大小 的团。由于构成了大小为 的团，因此这个 个点在之前一定两两连边。实际上在一个点和比自己编号更小的点的连边只会在这个点加入时出现，后续就不会新增了。

考虑和最新点连边的 个点中编号最大的点加入时构成的 团，发现从中删除一个点，加入新的点就可以构成这个团了。

例如这两张图，从蓝色团中删除了 ，并且加入了 。

我们如果把一个团看成一个点，可以感觉这大致构成了一个树的结构，因为你每次相当于是把一个点附加在原来的 团上。然而满足“删除一个点并加入一个点”的团可能有很多个。不过，影响这些点的其实是相同的 个节点的状态，我们只需要保证这个信息被传递下去了即可，所以随便钦定一个父亲并且保证其为树形结构即可，代码实现中可以钦定连边中编号最大的点加入时所在的团作为父亲。

例如，可以将第一张图转化成这个树（团的编号是团中最大节点的编号）

因此可以考虑从树形 dp 的角度去想。

然而，节点和节点之间的答案并不是完全独立的，这之间还有 个相交的节点。我们需要保证这张图不存在环。判断环的方法是查询连边的两个点在之前是否在一个连通块中，是则不能连边。连边之后还需要合并两个连通块。

换句话说，我们需要记录这 个节点的连通性信息。可以采用一种比较简单的记录方法：如果在同一个连通块就采用相同的数字，否则采用不同的数字。多种表示方法选取字典序最小的方法，采用哈希表记录状态即可。

例如，要编码这张图的联通状态：

就可以用这个序列来表示：

从子树转移到时候，我们先花 的代价枚举最大的点往哪些点连边。检查状态合法性时需要检查一下内容

• 确保最后一个点和至少一个其它点是联通的，因为这个点之后不会再有连边了。
• 加边之后不会产生环。

之后把最后一个点删掉，对状态重新编号并且和父节点合并，合并时也需要注意不能产生环。

对于 的情况，连通性方案有 种。但是实际我们只需要合并 和 的情况，因为从子树转移上来的时候删掉了一个点， 的时候只有 种方案。这其实就是贝尔数 和 的值。

实现方面，开始时只有 个节点，可以新建一个 号节点凑成 团。

虽然这个题目开了 ，但是我们的计算量大概是 并且有哈希等的开销，因此还是要注意常数的。

有以下几个常数优化技巧：

• 将状态压缩成 unsigned int，每 位存放一个数。
• 预处理状态的合并结果，转移时查表或者合并是缓存结果。
• 预处理 种合并结果，转移时查表。

代码在这里。