CF650E Clockwork Bomb
题目大意
给出两棵 (n) 个节点的树，每次操作可以把第一棵树的一条边删掉然后连另外两个点，且必须满足每次操作完之后仍是一棵树。
问最少需要多少步操作才能把第一棵树变成第二棵树（是完全相同，并不是同构），并输出方案。
数据范围：(1leq nleq 5 imes 10^5)。
本题题解
考虑两棵树（无向）边的集合。假设有 (k) 条公共的边（在两集合里均出现过），显然 (n - 1 - k) 是操作数的一个下界。下面我们通过构造，使答案取到这个下界。
首先，这 (k) 条公共的边，我们不去动它们。那么，可以把这些边连接的节点缩起来。我们称缩好的节点为“大点”，每个大点实际是原树上的一个连通块。可以发现如下性质：对于第一棵树的每个大点，总能在第二棵树上找到唯一一个对应的大点，使得两大点对应的连通块完全相同（节点的编号和连接方式，都完全一样）。换句话说：缩点后的两棵树，节点是一一对应的。
以节点 (1) 所在的大点为根，把两棵树变为有根树。定义树的叶子是没有儿子的节点（即，除非点数为 (1)，任务已经完成，否则根节点不是叶子）。
现在第一棵树上全都是要拆掉的边了。我们进行如下过程：
- 在第一棵树上，任意选一个叶子（大点），记为 (V)。考虑 (V) 对应的连通块，考虑原第一棵树上，和该连通块里至少一个点相连的边，这些边中，现在还剩下唯一一条是还没有被缩起来的：它就是连接 (V) 和 (V) 父亲的这条边。记这条边的两个端点分别为 (v, u)，其中 (v) 来自 (V)，(u) 来自 (V) 的父亲。
- 拆掉边 ((v, u))。
- 因为缩点后的两棵树节点是一一对应的，所以在第二棵树上，找到点 (V) 对应的点 (V')。(V') 不一定是叶子，所以它可能有很多连向外界的边。现在我们只要选择其中的一条（因为第二棵树是连通的，所以至少有一条从 (V') 出发连向外界的、还未被缩起来的边），并在第一棵树里加入这条边，就可以了。
- 方便起见，我们选择第二棵树上，连接 (V') 和 (V') 父亲的边。可以证明这条边一定存在：因为 (V) 是叶子，即 (V) 不包含节点 (1)，所以 (V') 也不包含节点 (1)，因此 (V') 不是第二棵树的根，故存在连接 (V') 和 (V') 父亲的边。记这条边为 ((v', u'))。
- 在第一棵树上连接 ((v', u'))，并把这条边缩起来。相当于删除了叶子 (V)，并将它并入了另一个节点。
综上，我们每次会删掉一个叶子。最终整棵树一定被缩到只剩一个节点。此时任务就完成了。
考虑如何实现上述过程。我们用并查集来进行缩点。
把初始时公共的边缩完后，我们在原第一棵树上 dfs。每次对于当前节点 (u) 的儿子 (v)，先递归下去。等返回时，(v) 已经变成了一个叶子。此时按上述方法处理边 ((v, u))：难点在于找出 (v')。发现它相当于，(v) 所在大点里，在第二棵树上深度最小的点。所以我们用并查集维护时，记录一下每个连通块内，在第二棵树上深度最小的点即可。
时间复杂度 (mathcal{O}(nalpha))。近似线性。
参考代码
实际提交时建议使用读入优化，详见本博客公告。
// problem: CF650E
#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }
const int MAXN = 5e5;
int n;
int fa[2][MAXN + 5], dep[2][MAXN + 5];
vector<int> G[2][MAXN + 5];
void dfs_init(int t, int u) {
for (int i = 0; i < SZ(G[t][u]); ++i) {
int v = G[t][u][i];
if (v == fa[t][u])
continue;
fa[t][v] = u;
dep[t][v] = dep[t][u] + 1;
dfs_init(t, v);
}
}
struct DSU {
int fa[MAXN + 5], sz[MAXN + 5];
int val[MAXN + 5], wei[MAXN + 5]; // wei 是权重, val 取权重最大者对应的值
int get_fa(int u) {
return (u == fa[u]) ? u : (fa[u] = get_fa(fa[u]));
}
int get_val(int u) {
return val[get_fa(u)];
}
void set_val(int u, int _val, int _wei) {
u = get_fa(u);
val[u] = _val;
wei[u] = _wei;
}
void upd_val(int u, int _val, int _wei) {
u = get_fa(u);
val[u] = (_wei > wei[u] ? _val : val[u]);
wei[u] = max(wei[u], _wei);
}
void unite(int u, int v, int _val, int _wei) {
u = get_fa(u);
v = get_fa(v);
if (u != v) {
if (sz[u] > sz[v])
swap(u, v);
fa[u] = v;
sz[v] += sz[u];
upd_val(v, val[u], wei[u]);
upd_val(v, _val, _wei);
} else {
upd_val(v, _val, _wei);
}
}
void init(int n) {
for (int i = 1; i <= n; ++i) {
fa[i] = i;
sz[i] = 1;
}
}
DSU() {}
} dsu;
struct Answer_t {
int u1, v1, u2, v2;
Answer_t() {}
Answer_t(int _u1, int _v1, int _u2, int _v2) {
u1 = _u1;
v1 = _v1;
u2 = _u2;
v2 = _v2;
}
};
int cnt;
Answer_t ans[MAXN + 5];
void dfs(int u) {
for (int i = 0; i < SZ(G[0][u]); ++i) {
int v = G[0][u][i];
if (v == fa[0][u])
continue;
dfs(v);
if (dsu.get_fa(u) != dsu.get_fa(v)) {
int x = dsu.get_val(v); // 连通块 v 中, 深度最小的点
ans[++cnt] = Answer_t(u, v, x, fa[1][x]);
dsu.unite(x, fa[1][x], fa[1][x], -dep[1][fa[1][x]]);
}
}
}
int main() {
cin >> n;
for (int t = 0; t <= 1; ++t) {
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
G[t][u].push_back(v);
G[t][v].push_back(u);
}
dfs_init(t, 1);
}
dsu.init(n);
for (int i = 1; i <= n; ++i) {
dsu.set_val(i, i, -dep[1][i]);
}
for (int u = 2; u <= n; ++u) {
int v = fa[0][u];
// 第一棵树中的无向边 (u, v)
if (fa[1][u] == v || fa[1][v] == u) {
// 第二棵树中也存在这条边
dsu.unite(u, v, u, -dep[1][u]); // 缩成一个大点
dsu.upd_val(u, v, -dep[1][v]);
}
}
dfs(1);
cout << cnt << endl;
for (int i = 1; i <= cnt; ++i) {
cout << ans[i].u1 << " " << ans[i].v1 << " " << ans[i].u2 << " " << ans[i].v2 << endl;
}
return 0;
}