C++ 基础：树上 LCA（最近公共祖先）求解方法

例题

问题描述

给定一棵有 N 个节点的树，每个节点有一个唯一的编号，从 1 到 N。树的根节点是 1 号节点。接下来，你会得到 Q 个查询。对于每个查询，你将得到两个节点的编号，你的任务是找到这两个节点的最低公共祖先。

输入格式

第一行包含一个整数 N，表示树的节点数。 接下来的 N-1 行，每行包含两个整数 U 和 V，表示节点 U 和节点 V 之间有一条边。 下一行包含一个整数 Q，表示查询的数量。 接下来的 Q 行，每行包含两个整数 A 和 B，表示你需要找到节点 A 和节点 B 的最低公共祖先。

输出格式

对于每个查询，输出一行，该行包含一个整数，表示两个节点的最近公共祖先。

样例输入

5
1 2
1 3
2 4
2 5
3
4 5
3 4
3 5

样例输出

2
1
1

样例说明

对于第一个查询，4 和 5 的最低公共祖先是 2。 对于第二个查询，3 和 4 的最低公共祖先是 1。 对于第三个查询，3 和 5 的最低公共祖先是 1。

测评数据规模

2 ≤ N ≤ 10^5，1 ≤ Q ≤ 10^4，1 ≤ U,V,A,B ≤ N，题目保证输入的边形成一棵树。

代码详解

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

const int N = 1e5 + 9;
int fa[N][24], dep[N];
vector<int> g[N];

void dfs(int x, int p) {
    dep[x] = dep[p] + 1;
    fa[x][0] = p;
    for (int i = 1; i <= 20; i++) {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    }
    for (const auto& y : g[x]) {
        if (y == p) continue;
        dfs(y, x);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; i >= 0; i--) {
        if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    }
    if (x == y) return x;
    for (int i = 20; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs(1, 0);
    int q; cin >> q;
    while (q--) {
        int x, y; cin >> x >> y;
        cout << lca(x, y) << '\n';
    }
    return 0;
}

方法二：Tarjan 求 LCA

Tarjan 算法求 LCA（基于并查集的离线算法）的核心优势在于高效处理多组查询，尤其适合需要一次性解决大量 LCA 查询的场景。

核心优势

1. 时间复杂度极低，适合大规模查询 Tarjan 算法是离线算法，其时间复杂度为 O(n + q)，其中 n 是树的节点数，q 是查询次数。对比倍增算法（在线算法，单次查询 O(logN)），当查询次数 q 很大时，Tarjan 算法的总效率更高。

2. 利用并查集实现'路径压缩'，合并与查询高效 算法核心依赖并查集的数据结构，通过 root(x) 快速查找节点所在集合的根，并用路径压缩优化查询效率。

3. 一次遍历处理所有查询，减少树的访问次数 算法通过深度优先搜索（DFS）遍历树一次，在回溯时完成并查集的合并，并同步处理所有与当前节点相关的查询。

4. 适用于静态树的批量查询场景 若问题中所有查询在处理前已知（离线场景），Tarjan 算法是最优选择之一。例如批量查询树上多对节点的 LCA。

5. 实现逻辑直观，依托 DFS 与并查集的天然契合 算法利用 DFS 的回溯特性：当遍历完一个节点的所有子树后，该节点与其子树的所有节点已被合并到同一集合，且集合的根为该节点。

总结

Tarjan 算法求 LCA 的核心优势是离线处理下的高效性，尤其在查询数量庞大时，其 O(n + q) 的时间复杂度远优于在线算法。但需注意其局限性：必须提前知晓所有查询（无法处理动态新增的查询），且依赖并查集和 DFS 的配合。

对比而言：

1. 若需要动态查询（查询逐步到来），优先选倍增算法；
2. 若查询一次性给出且数量大，Tarjan 算法是更优解。

代码

#include <utility>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
using namespace std;

const int N = 2e5 + 9;
int pre[N], ans[N];
vector<int> g[N];

struct Q {
    int x, id;
};
vector<Q> q[N];

int root(int x) {
    return pre[x] = (pre[x] == x ? x : root(pre[x]));
}

bitset<N> vis;

void tarjan(int x, int fa) {
    vis[x] = true;
    for (const auto& y : g[x]) {
        if (y == fa) continue;
        tarjan(y, x);
        pre[y] = x;
    }
    for (const auto& t : q[x]) {
        int y = t.x, id = t.id;
        if (vis[y]) ans[id] = root(y);
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) pre[i] = i;
    int m; cin >> m;
    for (int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        q[x].push_back({y, i});
        q[y].push_back({x, i});
    }
    tarjan(1, 0);
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
    return 0;
}