【模板】树算法之LCA(最近公共祖先)

1. Tarjan离线算法

时间复杂度：
• 预处理：O(n + Q)（Q为查询次数，使用路径压缩的并查集优化）。
• 总体效率：对大规模离线查询更快。
特点：
• 离线处理：需预先知道所有查询。
• 基于DFS遍历和并查集（路径压缩 + 按秩合并）。
• 常数因子较小，适合超大规模查询（如 Q > 1e6）。

示例代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

struct UnionFind {
    vector<int> parent, rank, ancestor;
    UnionFind(int n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        ancestor.resize(n + 1);
        FU(i, 0, n) parent[i] = ancestor[i] = i;
    }
    int find(int u) {
        return parent[u] == u ? u : parent[u] = find(parent[u]);
    }
    void unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;
        if (rank[u] < rank[v]) parent[u] = v;
        else {
            parent[v] = u;
            if (rank[u] == rank[v]) rank[u]++;
        }
    }
};

void tarjan(int u, int p, vector<vector<int>>& tree, vector<vector<pii>>& queries,
            vector<bool>& visited, UnionFind& uf, vector<int>& ans) {
    visited[u] = true;
    for (int v : tree[u]) {
        if (v != p) {
            tarjan(v, u, tree, queries, visited, uf, ans);
            uf.unite(u, v);
            uf.ancestor[uf.find(u)] = u;
        }
    }
    for (auto [v, idx] : queries[u]) {
        if (!visited[v] || ans[idx] != -1) continue;
        ans[idx] = uf.ancestor[uf.find(v)];
    }
}

signed main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<int>> tree(n + 1);
    FU(i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        tree[u].pb(v);
        tree[v].pb(u);
    }
    vector<vector<pii>> queries(n + 1);
    vector<int> ans(m, -1);
    FU(i, 0, m - 1) {
        int a, b;
        cin >> a >> b;
        queries[a].pb({b, i});
        queries[b].pb({a, i});
    }
    vector<bool> visited(n + 1, false);
    UnionFind uf(n);
    tarjan(s, -1, tree, queries, visited, uf, ans);
    for (int x : ans) cout << x << endl;
    return 0;
}

2. 倍增在线算法

• 时间复杂度：
• 预处理：O(n log n)（构建每个节点的2^k级祖先表）。
• 单次查询：O(log n)。
• 总体效率：对稀疏查询更灵活。
• 特点：
• 在线处理：支持实时查询。
• 实现简单，无需复杂数据结构。
• 内存占用较高（存储2^k祖先表）。

示例代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

const int MAX_LOG = 20;
vector<vector<int>> tree;
vector<array<int, MAX_LOG>> ancestor;
vector<int> depth;

void dfs(int u, int p) {
    ancestor[u][0] = p;
    for (int v : tree[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

void build(int n) {
    FU(k, 1, MAX_LOG - 1) {
        FU(u, 1, n) {
            int p = ancestor[u][k - 1];
            ancestor[u][k] = (p == -1) ? -1 : ancestor[p][k - 1];
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    FD(k, MAX_LOG - 1, 0) {
        if (depth[u] - (1 << k) >= depth[v])
            u = ancestor[u][k];
    }
    if (u == v) return u;
    FD(k, MAX_LOG - 1, 0) {
        if (ancestor[u][k] != -1 && ancestor[u][k] != ancestor[v][k]) {
            u = ancestor[u][k];
            v = ancestor[v][k];
        }
    }
    return ancestor[u][0];
}

signed main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    int n, m, s;
    cin >> n >> m >> s;
    tree.resize(n + 1);
    ancestor.resize(n + 1);
    depth.resize(n + 1, 0);
    FU(i, 1, n) ancestor[i].fill(-1);
    FU(i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        tree[u].pb(v);
        tree[v].pb(u);
    }
    depth[s] = 0;
    dfs(s, -1);
    build(n);
    while (m--) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }
    return 0;
}

关键对比

结论

• Tarjan更快：
若所有查询可以预先处理（如静态问题、批量查询），且Q极大（如竞赛题中Q与n同阶或更高），Tarjan算法显著更优。
• 倍增更灵活：
若需要实时响应查询或查询动态变化（如交互式场景），倍增法是更优选择。

根据实际需求选择算法：离线批处理用Tarjan，在线查询用倍增。

（本文由deepseek辅助生成）