挑战 NPC 题解

· · 题解

出题人答

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

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

首先我们将 x_1,x_2 同构的子树做贪心配对，如果在某个最终匹配方案中，

$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)$，足以通过本题。