本文原作于 2025 年 10 月 24 日，關(guān)于 Tarjan 算法的部分補充于 2025 年 11 月 4 日。

昨天看到歲歲似今朝以“學(xué)不成名誓不還”的勇氣學(xué) LCA，并感嘆“LCA 是我最嚴(yán)厲的母親”，心血來潮，也學(xué)了一下。翻看洛谷玲瑯滿目的題解，竟學(xué)會了三四種方法（最后一種于 2025 年 11 月 4 日補充），在此總結(jié)并進行比較，希望對大家和自己有所幫助。

倍增求 LCA

大家可能知道使用“暴力跳躍”來求 LCA 的方法：我們循環(huán)找深度較深的點的父節(jié)點，直到兩個節(jié)點深度相同，然后一起向上跳。倍增法基本也是這個思路，只是通過倍增優(yōu)化掉了逐步向上跳的過程。

我們設(shè) \(f_{u, j}\) 為節(jié)點 \(u\) 以上的第 \(2^j\) 個節(jié)點。顯然 \(f_{i, 0}\) 表示節(jié)點 \(i\) 的父節(jié)點，可以通過 DFS 求得所有 \(f_{u, 0}\)。想要求解每一個 \(i\) 節(jié)點跳 \(2^j\) 到的節(jié)點，等同于 \(i\) 節(jié)點先往上跳 \(2^{j-1}\) 步到的節(jié)點，再往上跳 \(2^{j-1}\) 步到的最終節(jié)點。因此可以得到狀態(tài)轉(zhuǎn)移方程：

求解 LCA 時，需要找到兩個點上面同一深度的點，如果兩個節(jié)點相同，則返回兩者之間任一節(jié)點，否則一起向上跳相同步數(shù)直至求出 LCA 為止。

模板題（洛谷 P3379）參考代碼：

#include <bits/stdc++.h>
typedef long long ll;
const int N = 1e6+10;
int f[N][30], dep[N], n, m, s;
std::vector<int> g[N];

void dfs(int u, int par) {
  f[u][0] = par;
  dep[u] = dep[par] + 1;
  for (auto &v: g[u]) {
    if (v != par) dfs(v, u);
  }
}

void init() {
  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 1; i <= n; i++) {
      f[i][j] = f[f[i][j-1]][j-1];
    }
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) std::swap(u, v);
  for (int i = 22; i >= 0; i--) {
    if (dep[f[u][i]] >= dep[v]) u = f[u][i];
  }
  if (u == v) return u;
  for (int i = 22; i >= 0; i--) {
    if (f[u][i] != f[v][i]) {
      u = f[u][i];
      v = f[v][i];
    }
  }
  return f[u][0];
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  std::cin >> n >> m >> s;
  for (int i = 1; i <= n-1; i++) {
    int a, b;
    std::cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(s, 0);
  init();
  for (int i = 1; i <= m; i++) {
    int a, b;
    std::cin >> a >> b;
    std::cout << lca(a, b) << '\n';
  }
  return 0;
}

DFS 序求 LCA

DFS 序是指對一棵樹進行深度優(yōu)先搜索得到的序列。DFN 是指樹上每個節(jié)點在 DFS 序中出現(xiàn)的位置。

設(shè)樹上兩個節(jié)點 \(u\)、\(v\) 的 LCA 為 \(d\)，且 \(u \neq v\)。不妨設(shè) \(\mathrm{dfn}(u) < \mathrm{dfn}(v)\)，顯然 \(v\) 不是 \(u\) 的祖先。分類討論：

1. \(u\) 不是 \(v\) 的祖先。 那么容易證明，DFS 序在 \(u\) 和 \(v\) 之間的節(jié)點均為 \(d\) 的后代。因此，我們可以找到滿足 \(\mathrm{dfn}(u) < v' < \mathrm{dfn}(v)\) 且深度最小的節(jié)點 \(v'\) ，那么 \(v'\) 的父節(jié)點就是 \(d\)。

2. \(u\) 是 \(v\) 的祖先。 如果還按照剛才的方法來求，可能會求得 \(u\) 的祖先，這不是我們想要的結(jié)果。但是如果把查詢區(qū)間變成 \([\mathrm{dfn}(u)+1, \mathrm{dfn}(v)]\)，就可以求得正確的 \(d\) 了。對于情況 1，由于 \(u \neq v'\)，所以還可以查詢 \([\mathrm{dfn}(u)+1, \mathrm{dfn}(v)]\) 。

需要特判的是，如果 \(u = v\)，直接返回 \(u\) 即可。

至于如何查找深度最小的節(jié)點 \(v\)，顯然要用 ST 表了。為了查詢方便，我們可以向 \(f_{i, 0}\) 中存入每個節(jié)點的父親，比較時取時間戳較小的節(jié)點。

模板題（洛谷 P3379）參考代碼：

#include <bits/stdc++.h>
typedef long long ll;
const int N = 5e5+10;
int n, m, s;
std::vector<int> g[N];
int st[N][20], lg[N], dfn[N], dn;
int get(int x, int y) {
  return dfn[x] < dfn[y]? x: y;
}
void dfs(int u, int par) {
  dn++;
  dfn[u] = dn;
  st[dn][0] = par;
  for (int &v: g[u]) {
    if (v != par) {
      dfs(v, u);
    }
  }
}
int lca(int u, int v) {
  if (u == v) return u;
  u = dfn[u], v = dfn[v];
  if (u > v) std::swap(u, v);
  u++; 
  int d = lg[v - u];
  return get(st[u][d], st[v - (1 << d) + 1][d]);
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  std::cin >> n >> m >> s;
  for (int i = 1; i <= n-1; i++) {
    int a, b;
    std::cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(s, 0);
  lg[1] = 0;
  for (int i = 2; i <= n; i++) {
    lg[i] = lg[i >> 1] + 1;
  }
  for (int j = 1; j <= lg[n]; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      st[i][j] = get(st[i][j-1], st[i + (1 << (j - 1))][j-1]);
    }
  }
  for (int i = 1; i <= m; i++) {
    int u, v;
    std::cin >> u >> v;
    std::cout << lca(u, v) << '\n';
  }
  return 0;
}

樹剖求 LCA

想學(xué)這個方法，首先得會樹剖。強烈推薦看一下 JZ8 的博客，他和我簡直心有靈犀啊 （JZ8 是誰？我不知道，我是永康喵喵） 。

首先先進行預(yù)處理，把重鏈剖分出來。然后不停地把當(dāng)前兩個節(jié)點中深度較深的那一個跳到其所屬的重鏈的頂端，直到兩個節(jié)點處于一條鏈上，此時深度較淺的節(jié)點就是 LCA。

配合上面的那篇博客，代碼顯然，不再贅述 （我絕對不會說是因為我太懶了沒寫） 。

Tarjan 算法

在學(xué)本算法前，請先確保自己會并查集。

Tarjan 算法是一種借助并查集離線求解 LCA 的算法。這種算法的一般流程是：對樹進行 DFS，在回溯時對當(dāng)前節(jié)點及其父節(jié)點在并查集中進行合并。如果當(dāng)前位于節(jié)點 \(u\) 時，節(jié)點 \(v\) 已被訪問，且要查詢節(jié)點 \(v\) 和節(jié)點 \(u\) 的 LCA 時，就返回 \(\mathrm{find}(u)\)。

流程非常簡單好記，但是有幾個坑點需要注意：

1. 不要進行按秩合并，始終將并查集中子節(jié)點的 par 設(shè)置為父節(jié)點。
2. 為了快速查詢并處理詢問，可以用一個存有 pair 的 vector 數(shù)組來存儲詢問。記第 \(i\) 個詢問為查詢 \(u\) 和 \(v\) 的 LCA，則 queries[u].push_back({v, i}), queries[v].push_back({u, i});。

#include <bits/stdc++.h>
typedef long long ll;
const int N = 5e5+10;
int ans[N], n, m, s;
bool vis[N];
std::vector<int> g[N];
std::vector<std::pair<int, int> > queries[N];

struct UF {
  int par[N], siz[N];
  void init() {
    for (int i = 1; i <= n; i++) {
      par[i] = i, siz[i] = 1;
    }
  }
  int find(int u) {
    return u == par[u] ? u : (par[u] = find(par[u]));
  }
  void merge(int u, int v) {
    u = find(u), v = find(v);
    par[u] = v;
  }
} uf;

void tarjan(int u) {
  vis[u] = true;
  for (auto &v: g[u]) {
    if (vis[v]) continue;
    tarjan(v);
    uf.merge(v, u);
  }
  for (auto &q : queries[u]) {
    int v = q.first;
    int id = q.second;
    if (vis[v]) ans[id] = uf.find(v);
  }
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  std::cin >> n >> m >> s;
  for (int i = 1; i <= n - 1; i++) {
    int u, v;
    std::cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  uf.init();
  for (int i = 1; i <= m; i++) {
    int u, v;
    std::cin >> u >> v;
    if (u == v) ans[i] = u;
    else {
      queries[u].push_back({v, i});
      queries[v].push_back({u, i});
    }
  }
  tarjan(s);
  for (int i = 1; i <= m; i++) {
    std::cout << ans[i] << '\n';
  }
  return 0;
}

比較

下表部分由 DeepSeek 生成。

注：\(\alpha(x)\) 為反阿克曼函數(shù)，增長率極慢，一般可當(dāng)作常數(shù)看待。

總而言之，建議初學(xué)者先學(xué)習(xí)倍增法，因為其代碼實現(xiàn)簡單、靈活性較好。如果要追求更高的性能，推薦使用樹剖法、DFS 序法或 Tarjan 算法（尤其在需要處理大量查詢時）。