自动搬运

查看原文

来自洛谷，原作者为

	EternalAlexander 魔力的碎片都不再拥有的少年

搬运于2025-08-24 22:20:17，当前版本为作者最后更新于2020-04-16 22:18:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

性质

首先观察到，生成的图 $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$ 中的祖先节点，否则将会出现连线交叉的情况。因此，这些 节点都不早于 $u$ 加入决策集合。矛盾。

做法

每个节点会向自己的某个祖先节点连边，并且两条连线不能交叉。我们要计算这样的方案数。

考虑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)$ 做法。