题解 - Luogu P14464 海底列車（collapse）

愚蠢的 $2n$ 次数做法，除了代码短一点点和好想就没啥优势了。

简述题意

给两棵有根树 $T_1,T_2$，每次可以交换 $T_1$ 中某两个距离为偶的点的父亲，问能否在 $2n$ 次操作内将 $T_1$ 变成 $T_2$。$n\le 5000$。

解法

对于一棵树，黑白染色，两种颜色的点的度数集合分别记为 $S_0,S_1$，则 $(S_0,S_1)$ 这个无序二元组相同的两棵树，他们都是可以互相转化的。这个东西的必要性是显然的（操作不会改变点的度数），我们考虑用构造把它的充分性得出来。

考虑只根据 $(S_0,S_1)$ 生成一棵树 $T_x$，然后让等价类里面所有的 $T$ 都可以在 $n$ 次操作之内和它转化，我们就可以得到 $T_1\to T_x\to T_2$。

我们发现只要每次我们在 $T_x$ 上接上去一个叶子，$T$ 上就一定可以操作。具体来说，每次操作是：

• 如果 $1\in S_0$，那么把这个 $1$ 对应的节点和 $S_1$ 中一个用某种方式定下来的非 $1$ 度点相连，在此之后这条边应当视作不存在（毕竟它不能再发生改变了）；
• 否则必定有 $1\in S_1$，对称地操作即可。

当我想要在 $T_1,T_2$（以下直接称为 $T$）连起来一条边 $x\to y$，其中 $x$ 是叶子：

• 如果这条边存在，pass；
• 令 $y\to x$ 路径上的第二个点是 $p$，$x\to y$ 路径上的第二个点是 $s$，$y$ 的任意一个不是 $p$ 的邻点是 $t$，那么一次操作我们进行 $(x,t)$。
• 容易发现由于 $x$ 度数为 $1$，每次只是把一个叶子剥出去，不影响后续操作。

模拟以上过程需注意绝对不可以让 $T$ 的编号影响其和 $T_x$ 之间的转化。

暴力模拟，复杂度 $O(n^2)$。