题解：P14464 海底列車（collapse）

xxxxxzy · 2025-11-08 15:49:01 · 题解

为什么 T1 没人过.jpg。

结论是如果两棵树黑白染色后，黑白点度数的可重集对应相同就可以操作成功。

考虑对两棵树同时匹配，首先我们对两棵树都找到一个叶子节点 a_0,b_0，进行函数 \text{match}(a_0,b_0)。下记 A(u),B(u) 代表树 S,T 中节点 u 的度数，以及 col_x 代表到根的距离对 2 取模的值。

当进行 \text{match}(a,b) 的时候，如果 A(a) \ne B(b)，则考虑对 a 进行操作。遍历 1 到 n 的所有点，任意找到一个未匹配的点 a' 使得 A(a')=B(b) \wedge col_a=col_{a'}。分类讨论：

这样看起来似乎就做完了，不过我们还需要讨论一个 corner case：

• 如果 a' 在 a 的子树，且 a' 没有儿子，继续分类讨论：
  • 如果 a 的子树外存在未匹配的点 a'' 满足 A(a'')=B(b) 且 col_a=col_{a'}，选择 a'' 即可。
  • 否则一定存在 p 使得 A(p)=1 \wedge col_p \ne col_a 对 (fa_{a'},p) 进行操作，然后对 (a,p) 进行操作。

实现非常简单，每次找到一对未匹配的儿子匹配就行，时间 O(n^2)，应该可以做到更低的复杂度，但是没必要了，代码大概 5K 左右，很好写。

Bonus：这个题有一个基于二阶毛毛虫代表元的做法，代码我写了 10K，感兴趣的读者可以写着玩玩。