自动搬运

查看原文

来自洛谷，原作者为

	大头 YSGH牛逼

搬运于2025-08-24 22:39:37，当前版本为作者最后更新于2022-09-30 14:59:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

出题人答

首先求出 $G,H$ 每颗子树的哈希值用于判断子树同构问题。接下来给定分别在 $G,H$ 中的节点 $x_1,x_2$, 假定我们需要递归的判定如下子问题，设为 $f(x_1,x_2)$:

是否存在这么一种运行方式，使得：

• 重复如下过程若干轮，每一轮选择 $G$ 以 $x_1$ 为根的子树的一个叶子，并将其移除。
• 删除上述节点后，剩余的有根子树和 $H$ 以 $x_2$ 为根的子树同构。

首先我们将 $x_1,x_2$ 同构的子树做贪心配对，如果在某个最终匹配方案中， $G$ 中子树 $a$ 在删除若干节点后和 $H$ 的子树 $b$ 同构， $G$ 中子树 $b$ 在删除若干节点后和 $H$ 的子树 $c$ 同构(相同的小写字母代表着是同构的有根子树)，则我们可以直接让 $H$ 中子树 $a$ 在删除后和 $H$ 的子树 $c$ 同构，同时不去修改 $G$ 的子树 $b$ 并且和 $H$ 的子树 $b$ 匹配。上述操作合法性不难得到。

因而不妨假定最后未匹配的子树个数至多为 $k$ (由于我们只修改了 $k$ 个节点，若不然必然无解)，直接暴力枚举 $k^2$ 个可能的子树同构对后检查是否存在完美匹配即可。

接下来我们可以增加一些剪枝:

• 如果两颗子树哈希值相同，则返回匹配
• 如果两颗子树哈希值不同，大小相同，则返回不匹配
• 如果 $G$ 的子树大小小于 $H$ 的子树大小，则返回不匹配
• 假设已经知道未匹配的子树数为 $m$，两棵树大小差为 $k$。如果子问题中两颗子树大小差大于 $k - (m - 1)$，则返回不匹配。

接下来我们证明在采用上述剪枝的前提下，对于每一个 $G,H$ 中的节点，其出现在求解子问题中的次数不会很多即可。我们递归地证明，假定我们搜索到了子问题 $f(x_G,y_H)$，两棵树的大小差为 $k$，则对于任意一个属于子树 $x_G$ 的节点 $x$，至多只有 $\max(1,2^{k-1})$ 个可能的属于子树 $y_H$ 的节点 $x_2 \in V_2$，使得在搜索过程中搜索到了子问题 $(x,y)$.

• 如果 $k = 0$，我们只需要直接判定两棵树的哈希值是否相同，显而易见其甚至不需要递归操作，性质成立。
• 如果 $k = 1$，根据约束条件知道如果可以匹配则我们每个子树中都至多能够找到 $1$ 个匹配不到的节点。因而产生的子问题唯一，从而每个节点至多出现在一次询问中，性质成立
• 如果 $k \neq 1$，假定其有 $m$ 个未匹配问题。如果 $m = 1$ 则子问题唯一对，对子问题进行归纳即可。如果 $m > 1$，则每个没有被剪掉的子问题中，两棵子树大小之差至多为 $k - (m - 1) \ge 1$，同时每一个 $x$ 最多出现在其所在的子树出现的 $m$ 个子问题之中。因而根据归纳，搜索到的子问题至多有 $\max_{m > 2} m 2^{k - (m - 1) - 1} = 2^{k-1}$ 个，归纳成立。

因此我们可以直接采用类似于归并的方式求出不匹配的子树，然后根据上述剪枝规则剪枝即可。检查完美匹配可以匈牙利，可以 Hall Theorem,可以 爆搜，在 $k$ 较小的情况下几乎只是常数的区别。

以 Hall Thm 为例，其总时间复杂度为 $O(n 4^k)$，足以通过本题。