「OOI 2016 Day 1」时钟装置 题解

问题分析

我们有两棵树 $T_1$（初始树）和 $T_2$（目标树），每次操作可以：

1. 删除一条边 $(a,b)$
2. 立即添加一条边 $(c,d)$
3. 保持树的结构（无环、连通）

关键观察：
如果一条边 $e$ 在 $T_1$ 但不在 $T_2$ 中，那么它必须被替换。
如果一条边 $e$ 在 $T_2$ 但不在 $T_1$ 中，那么我们需要添加它。

算法思路

核心思想

考虑 $T_2$ 中的每条边 $(u,v)$：

• 如果 $(u,v)$ 不在 $T_1$ 中，那么在 $T_1$ 中 $u$ 到 $v$ 的路径上一定存在某条边可以被替换为 $(u,v)$

具体步骤

1. 预处理：

   • 以 $T_2$ 为基准，为每个节点计算父节点、深度、DFS序
   • 在 $T_1$ 上也建立类似结构

2. 寻找操作：

   • 遍历 $T_2$ 中的每条边 $(u,v)$
   • 如果 $(u,v)$ 不在 $T_1$ 中：
     • 在 $T_1$ 中找到 $u$ 到 $v$ 路径上的一条边 $e$，且 $e$ 不在 $T_2$ 中
     • 执行操作：删除 $e$，添加 $(u,v)$

3. 实现细节：

   • 使用 DFS 序和 LCA 来快速判断边的关系
   • 用并查集或树链剖分来维护可删除的边

复杂度分析

时间复杂度

• 预处理：$O(n)$
• 寻找操作：$O(n \log n)$（使用 LCA）
• 总复杂度：$O(n \log n)$

空间复杂度

• $O(n)$ 存储树结构和辅助信息

代码框架

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

const int MAXN = 500005;

vector<int> T1[MAXN], T2[MAXN];
set<pair<int,int>> edges1, edges2;
int parent1[MAXN], parent2[MAXN], depth1[MAXN], depth2[MAXN];

void dfs1(int u, int p) {
    parent1[u] = p;
    depth1[u] = depth1[p] + 1;
    for (int v : T1[u]) {
        if (v != p) dfs1(v, u);
    }
}

void dfs2(int u, int p) {
    parent2[u] = p;
    depth2[u] = depth2[p] + 1;
    for (int v : T2[u]) {
        if (v != p) dfs2(v, u);
    }
}

int main() {
    int n;
    cin >> n;
    
    // 读入初始树 T1
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        T1[x].push_back(y);
        T1[y].push_back(x);
        edges1.insert({min(x,y), max(x,y)});
    }
    
    // 读入目标树 T2
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        T2[x].push_back(y);
        T2[y].push_back(x);
        edges2.insert({min(x,y), max(x,y)});
    }
    
    // 预处理
    dfs1(1, 0);
    dfs2(1, 0);
    
    vector<tuple<int,int,int,int>> operations;
    
    // 寻找需要添加的边（在T2中但不在T1中）
    for (auto& e : edges2) {
        int u = e.first, v = e.second;
        if (!edges1.count(e)) {
            // 需要添加边(u,v)，在T1中找到可删除的边
            // 这里需要实现路径查找逻辑
            // 简化版：找到u到v路径上的一条不在T2中的边
            int a = u, b = v;
            // 调整深度，让a更深
            if (depth1[a] < depth1[b]) swap(a, b);
            
            // 找到a向上到b路径上的一条边
            int del_u = a, del_v = parent1[a];
            operations.push_back({del_u, del_v, u, v});
            
            // 更新T1结构（在实际代码中需要维护）
        }
    }
    
    cout << operations.size() << "\n";
    for (auto& op : operations) {
        cout << get<0>(op) << " " << get<1>(op) << " " 
             << get<2>(op) << " " << get<3>(op) << "\n";
    }
    
    return 0;
}

注意事项

1. 可行性判断：如果两棵树的连通分量不同，则输出 $-1$
2. 操作顺序：某些操作顺序可能更优，但题目允许任意最优解
3. 实现复杂度：实际实现需要使用高效的数据结构来处理 $n \leq 500000$ 的情况

总结

本题的关键在于理解树边替换的可行性条件，通过系统性地将 $T_1$ 转换为 $T_2$，每次操作保持树结构不变，最终达到目标状态。