Contest Info

practice link

Solutions

C. Clockwork Bomb

题目大意：给出两棵 \(n\) 个点的树，要求通过一些操作使第一棵树变成第二棵 树。每次操作断开一条边，再添加一条边。必须保证任意时刻是一棵树，输出一个合法的操作序列。

题解：如果一条边在两棵树中都出现，那么显然我们不会对其进行操作。我们给每个点维护一个 vector，存放该点连的只在第二棵树中出现的边。然后在第一棵树上进行 dfs，递归回溯的时候，以 \(u\) 的儿子节点 \(v\) 为根的子树已经处理过。我们考虑 \((u, v)\) 这条边：

• 若 \((u, v)\) 在两棵树中均出现，我们合并 \(u, v\) 两点的 vector
• 否则，我们断开 \((u, v)\) 这条边，在 \(v\) 所在并查集的 vector 中选择一条还未连接的边，进行连接。然后合并相应的并查集和 vector