题解 P6383 【『MdOI R2』Resurrection】

· · 题解

好像没啥比较靠谱的题解，估计一堆过掉的人都是猜的结论，早知道出构造了。

性质

首先观察到，生成的图 G 是一棵树，且假如把原树和新树都看作以 n 为根的有根树，那么新树的任意节点的父节点都是它在原树中的祖先节点。

我们考虑什么样的树可能是生成的新树。

一个必要条件是，任意两个祖先-后代节点到父边的连线要么相离，要么某一条包含另一条。也就是说，不存在 u，v，u 在 G 中的父节点是 x，v 是 y，满足 u 是 v 的祖先，且 y 是 u 的祖先，且 x 是 y 的祖先。

我们考虑 u 的父边被断开的时候，在那之前，u 到 x 之间的任何边都不能被断开，否则 u 到 x 的连边将无法完成。又因为，y 被包含在 u 到 x 的路径中，v 所在联通块最大点至少是 x，其到 y 的连线不可能在这之前完成。而在这之后，v 和 y 不再联通，不可能相互连边。

同时，这个条件是充分的。考虑这样构造方案：维护一个决策集合，一开始只有根的子节点。

每次取决策集合中编号最小的点，断开它在原树中到父节点的边，然后将它在新树中的子节点加入决策集合。

这样构造的方案一定是合法的，考虑点 u 到父节点的连边，这个点不可能比它的目标父节点 v 大，因为只有在 v 到父节点的边被断开后 u 才可能加入决策集合。

同时这个点也不可能比 v 小，假如这个点比 v 小，那么一定有 u-v 中某一条边被断开了，又因为这些点的编号都比 u 大，必须它们比 u 先加入决策集合才能出现这种情况。

然而，根据这个条件的必要性， v 一定是这些节点在 G 中的祖先节点，否则将会出现连线交叉的情况。因此，这些 节点都不早于

## 做法 每个节点会向自己的某个祖先节点连边，并且两条连线不能交叉。我们要计算这样的方案数。 考虑dp。我们记 $f_{i,j}$ 表示考虑到节点 $i$，祖先中有 $j$ 个可以向其连边的节点时，子树中连边的方案数。 考虑枚举点 $u$ 和从下往上数，第 $x$ 个节点连边。那么，这条连线会覆盖掉 $x-1$ 个可以连边的节点，然后对于子树中的所有节点，$u$ 都是一个可以连边的节点。 可以写出转移：$f_{i,j} = \sum_{x=1}^j \prod f_{v,j-(x-1)+1}$，前缀和优化即可得到 $O(n^2)$ 做法。