题解：P14464 海底列車（collapse）

为什么 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：

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

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