「NordicOI 2017」Subway 题解

问题分析

我们需要将一棵旧树通过边替换操作转换成新树，每次操作：

• 删除一条旧边
• 添加一条新边
• 保持图始终连通

目标是用最少的操作次数完成转换。

算法思路与代码实现

核心观察

最少操作次数 = 两棵树不同的边数

1. 数据结构设计

struct Edge {
	int u, v, id;  // 边的端点和唯一标识
};

struct UF {  // 并查集维护连通分量
	vi v, deg;
	vector<vector<Edge>> ed, ed2;  // ed: 需要删除的边, ed2: 需要添加的边
	UF(int n) : v(n, -1), deg(n), ed(n), ed2(n) {}
	int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
	void join(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return;
		if (-v[a] < -v[b]) swap(a, b);
		v[a] += v[b];
		deg[a] += deg[b];
		ed[a].insert(ed[a].end(), all(ed[b]));
		ed2[a].insert(ed2[a].end(), all(ed2[b]));
		v[b] = a;
	}
};

设计原理：

• 使用并查集维护连通分量
• ed 存储需要删除的旧边
• ed2 存储需要添加的新边
• deg 记录每个连通分量的"度数"

2. 输入处理与差异识别

int main() {
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	int N;
	cin >> N;

	UF uf(N);
	set<pii> source, target;

	// 读取旧边
	rep(i,0,N-1) {
		cin >> u >> v;
		if (u > v) swap(u, v);
		source.insert(pii(u,v));
	}
	
	// 读取新边，识别共同边
	rep(i,0,N-1) {
		cin >> u >> v;
		if (u > v) swap(u, v);
		if (source.count(pii(u,v))) {
			uf.join(u, v);  // 共同边直接合并连通分量
			source.erase(pii(u,v));
		}
		else
			target.insert(pii(u,v));  // 新树特有的边
	}

关键步骤：

• 规范化边表示（确保 u < v）
• 识别共同边并立即连通对应节点
• 分离出需要删除的边（source）和需要添加的边（target）

3. 构建边集合与初始化

int delta = sz(source);  // 不同的边数
assert(delta == sz(target));  // 确保两集合大小相同

vector<bool> dead;
int eid = 0;

// 分配需要删除的边到对应连通分量
trav(e, source) {
	tie(u,v) = e;
	Edge edg = {u, v, eid++};
	uf.ed[uf.find(u)].push_back(edg);
	uf.ed[uf.find(v)].push_back(edg);
	dead.push_back(false);
}

// 分配需要添加的边到对应连通分量  
trav(e, target) {
	tie(u,v) = e;
	Edge edg = {u, v, eid++};
	uf.ed2[uf.find(u)].push_back(edg);
	uf.ed2[uf.find(v)].push_back(edg);
	dead.push_back(false);
}

分配策略：将每条边分配到其端点所在的连通分量中，便于后续处理。

4. 叶子优先处理策略

vi leaves;
rep(i,0,N) {
	uf.deg[i] = sz(uf.ed[i]);  // 每个连通分量的"度数"
	if (uf.deg[i] == 1) leaves.push_back(i);  // 叶子连通分量
}

vector<tuple<int, int, int, int>> out;  // 存储操作序列

贪心思想：从度数最小的连通分量（叶子）开始处理，确保操作可行性。

5. 核心替换算法

while (!leaves.empty()) {
	int theLeaf = leaves.back();
	int comp = uf.find(theLeaf);
	leaves.pop_back();

	if (uf.ed[comp].empty()) continue;
	
	// 获取要删除的边
	Edge e = uf.ed[comp].back();
	uf.ed[comp].pop_back();
	if (dead[e.id]) {
		leaves.push_back(theLeaf);
		continue;
	}

	int x = e.u, y = e.v;
	if (uf.find(x) != comp) swap(x, y);
	assert(uf.find(x) == comp);  // 确保x在当前连通分量

	// 找到要添加的新边
	Edge e2;
	for (;;) {
		assert(uf.ed2[comp].size() >= 1);
		e2 = uf.ed2[comp].back();
		uf.ed2[comp].pop_back();
		if (!dead[e2.id]) break;  // 找到可用的新边
	}

	int x2 = e2.u, y2 = e2.v;
	if (uf.find(x2) != comp) swap(x2, y2);
	assert(uf.find(x2) == comp);  // 确保x2在当前连通分量

	// 记录替换操作
	out.emplace_back(x, y, x2, y2);
	dead[e.id] = dead[e2.id] = true;
	
	// 更新度数
	--uf.deg[comp];
	if (--uf.deg[uf.find(y)] == 1) {
		leaves.push_back(uf.find(y));  // 新的叶子连通分量
	}
	
	// 合并连通分量
	uf.join(x, y2);
}

算法保证：

1. 连通性：删除边后立即添加连接同一分量的新边
2. 可行性：叶子优先确保总能找到可执行的操作
3. 完整性：处理所有差异边

6. 输出结果

cout << sz(out) << endl;
trav(t, out) {
	int a,b,c,d;
	tie(a,b,c,d) = t;
	cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
}
assert(sz(out) == delta);  // 验证操作次数正确性

复杂度分析

• 时间复杂度：$O(N \alpha(N))$，其中 $\alpha$ 是反阿克曼函数
• 空间复杂度：$O(N)$

算法优势

$1.$ 理论最优：操作次数等于差异边数，达到理论下界

$2.$ 实践高效：利用并查集和贪心策略，处理大规模数据

$3.$ 正确性保证：严格的断言验证算法正确性

该算法通过并查集维护连通性 + 叶子优先贪心策略，完美解决了树重构问题。