最近公共祖先

定義

最近公共祖先簡稱 LCA（Lowest Common Ancestor）。兩個節點的最近公共祖先，就是這兩個點的公共祖先裏面，離根最遠的那個。 為了方便，我們記某點集 \(S=\{v_1,v_2,\ldots,v_n\}\) 的最近公共祖先為 \(\text{LCA}(v_1,v_2,\ldots,v_n)\) 或 \(\text{LCA}(S)\)。

性質

本節 性質 部分內容翻譯自 wcipeg，並做過修改。

1. \(\text{LCA}(\{u\})=u\)；
2. \(u\) 是 \(v\) 的祖先，當且僅當 \(\text{LCA}(u,v)=u\)；
3. 如果 \(u\) 不為 \(v\) 的祖先並且 \(v\) 不為 \(u\) 的祖先，那麼 \(u,v\) 分別處於 \(\text{LCA}(u,v)\) 的兩棵不同子樹中；
4. 前序遍歷中，\(\text{LCA}(S)\) 出現在所有 \(S\) 中元素之前，後序遍歷中 \(\text{LCA}(S)\) 則出現在所有 \(S\) 中元素之後；
5. 兩點集並的最近公共祖先為兩點集分別的最近公共祖先的最近公共祖先，即 \(\text{LCA}(A\cup B)=\text{LCA}(\text{LCA}(A), \text{LCA}(B))\)；
6. 兩點的最近公共祖先必定處在樹上兩點間的最短路上；
7. \(d(u,v)=h(u)+h(v)-2h(\text{LCA}(u,v))\)，其中 \(d\) 是樹上兩點間的距離，\(h\) 代表某點到樹根的距離。

求法

樸素算法

過程

可以每次找深度比較大的那個點，讓它向上跳。顯然在樹上，這兩個點最後一定會相遇，相遇的位置就是想要求的 LCA。 或者先向上調整深度較大的點，令他們深度相同，然後再共同向上跳轉，最後也一定會相遇。

性質

樸素算法預處理時需要 dfs 整棵樹，時間複雜度為 \(O(n)\)，單次查詢時間複雜度為 \(\Theta(n)\)。如果樹滿足隨機性質，則時間複雜度與這種隨機樹的期望高度有關。

倍增算法

過程

倍增算法是最經典的 LCA 求法，他是樸素算法的改進算法。通過預處理 \(\text{fa}_{x,i}\) 數組，遊標可以快速移動，大幅減少了遊標跳轉次數。\(\text{fa}_{x,i}\) 表示點 \(x\) 的第 \(2^i\) 個祖先。\(\text{fa}_{x,i}\) 數組可以通過 dfs 預處理出來。

現在我們看看如何優化這些跳轉： 在調整遊標的第一階段中，我們要將 \(u,v\) 兩點跳轉到同一深度。我們可以計算出 \(u,v\) 兩點的深度之差，設其為 \(y\)。通過將 \(y\) 進行二進制拆分，我們將 \(y\) 次遊標跳轉優化為「\(y\) 的二進制表示所含 1 的個數」次遊標跳轉。 在第二階段中，我們從最大的 \(i\) 開始循環嘗試，一直嘗試到 \(0\)（包括 \(0\)），如果 \(\text{fa}_{u,i}\not=\text{fa}_{v,i}\)，則 \(u\gets\text{fa}_{u,i},v\gets\text{fa}_{v,i}\)，那麼最後的 LCA 為 \(\text{fa}_{u,0}\)。

性質

倍增算法的預處理時間複雜度為 \(O(n \log n)\)，單次查詢時間複雜度為 \(O(\log n)\)。 另外倍增算法可以通過交換 fa 數組的兩維使較小維放在前面。這樣可以減少 cache miss 次數，提高程序效率。

例題

HDU 2586 How far away? 樹上最短路查詢。

可先求出 LCA，再結合性質 \(7\) 進行解答。也可以直接在求 LCA 時求出結果。

參考代碼

#include <cstdio>
#include <cstring>
#include <vector>

#define MXN 40005
using namespace std;
std::vector<int> v[MXN];
std::vector<int> w[MXN];

int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;

// dfs，用来为 lca 算法做准备。接受两个参数：dfs 起始节点和它的父亲节点。
void dfs(int root, int fno) {
  // 初始化：第 2^0 = 1 个祖先就是它的父亲节点，dep 也比父亲节点多 1。
  fa[root][0] = fno;
  dep[root] = dep[fa[root][0]] + 1;
  // 初始化：其他的祖先节点：第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
  // 2^(i-1) 的祖先节点。
  for (int i = 1; i < 31; ++i) {
    fa[root][i] = fa[fa[root][i - 1]][i - 1];
    cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
  }
  // 遍历子节点来进行 dfs。
  int sz = v[root].size();
  for (int i = 0; i < sz; ++i) {
    if (v[root][i] == fno) continue;
    cost[v[root][i]][0] = w[root][i];
    dfs(v[root][i], root);
  }
}

// lca。用倍增算法算取 x 和 y 的 lca 节点。
int lca(int x, int y) {
  // 令 y 比 x 深。
  if (dep[x] > dep[y]) swap(x, y);
  // 令 y 和 x 在一个深度。
  int tmp = dep[y] - dep[x], ans = 0;
  for (int j = 0; tmp; ++j, tmp >>= 1)
    if (tmp & 1) ans += cost[y][j], y = fa[y][j];
  // 如果这个时候 y = x，那么 x，y 就都是它们自己的祖先。
  if (y == x) return ans;
  // 不然的话，找到第一个不是它们祖先的两个点。
  for (int j = 30; j >= 0 && y != x; --j) {
    if (fa[x][j] != fa[y][j]) {
      ans += cost[x][j] + cost[y][j];
      x = fa[x][j];
      y = fa[y][j];
    }
  }
  // 返回结果。
  ans += cost[x][0] + cost[y][0];
  return ans;
}

void Solve() {
  // 初始化表示祖先的数组 fa，代价 cost 和深度 dep。
  memset(fa, 0, sizeof(fa));
  memset(cost, 0, sizeof(cost));
  memset(dep, 0, sizeof(dep));
  // 读入树：节点数一共有 n 个，查询 m 次，每一次查找两个节点的 lca 点。
  scanf("%d %d", &n, &m);
  // 初始化树边和边权
  for (int i = 1; i <= n; ++i) {
    v[i].clear();
    w[i].clear();
  }
  for (int i = 1; i < n; ++i) {
    scanf("%d %d %d", &a, &b, &c);
    v[a].push_back(b);
    v[b].push_back(a);
    w[a].push_back(c);
    w[b].push_back(c);
  }
  // 为了计算 lca 而使用 dfs。
  dfs(1, 0);
  for (int i = 0; i < m; ++i) {
    scanf("%d %d", &a, &b);
    printf("%d\n", lca(a, b));
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) Solve();
  return 0;
}

Tarjan 算法

過程

Tarjan 算法是一種 離線算法，需要使用 並查集 記錄某個結點的祖先結點。做法如下：

1. 首先接受輸入邊（鄰接鏈表）、查詢邊（存儲在另一個鄰接鏈表內）。查詢邊其實是虛擬加上去的邊，為了方便，每次輸入查詢邊的時候，將這個邊及其反向邊都加入到 queryEdge 數組裏。
2. 然後對其進行一次 DFS 遍歷，同時使用 visited 數組進行記錄某個結點是否被訪問過、parent 記錄當前結點的父親結點。
3. 其中涉及到了 回溯思想，我們每次遍歷到某個結點的時候，認為這個結點的根結點就是它本身。讓以這個結點為根節點的 DFS 全部遍歷完畢了以後，再將這個結點的根節點設置為這個結點的父一級結點。
4. 回溯的時候，如果以該節點為起點，queryEdge 查詢邊的另一個結點也恰好訪問過了，則直接更新查詢邊的 LCA 結果。
5. 最後輸出結果。

性質

Tarjan 算法需要初始化並查集，所以預處理的時間複雜度為 \(O(n)\)。

樸素的 Tarjan 算法處理所有 \(m\) 次詢問的時間複雜度為 \(O(m \alpha(m+n, n) + n)\)，。但是 Tarjan 算法的常數比倍增算法大。存在 \(O(m + n)\) 的實現。

注意

並不存在「樸素 Tarjan LCA 算法中使用的並查集性質比較特殊，單次調用 find() 函數的時間複雜度為均攤 \(O(1)\)」這種説法。

以下的樸素 Tarjan 實現複雜度為 \(O(m \alpha(m+n, n) + n)\)。如果需要追求嚴格線性，可以參考 Gabow 和 Tarjan 於 1983 年的論文。其中給出了一種複雜度為 \(O(m + n)\) 的做法。

實現

參考代碼

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

class Edge {
 public:
  int toVertex, fromVertex;
  int next;
  int LCA;
  Edge() : toVertex(-1), fromVertex(-1), next(-1), LCA(-1){};
  Edge(int u, int v, int n) : fromVertex(u), toVertex(v), next(n), LCA(-1){};
};

const int MAX = 100;
int head[MAX], queryHead[MAX];
Edge edge[MAX], queryEdge[MAX];
int parent[MAX], visited[MAX];
int vertexCount, queryCount;

int find(int x) {
  if (parent[x] == x) {
    return x;
  } else {
    return parent[x] = find(parent[x]);
  }
}

void tarjan(int u) {
  parent[u] = u;
  visited[u] = 1;

  for (int i = head[u]; i != -1; i = edge[i].next) {
    Edge& e = edge[i];
    if (!visited[e.toVertex]) {
      tarjan(e.toVertex);
      parent[e.toVertex] = u;
    }
  }

  for (int i = queryHead[u]; i != -1; i = queryEdge[i].next) {
    Edge& e = queryEdge[i];
    if (visited[e.toVertex]) {
      queryEdge[i ^ 1].LCA = e.LCA = find(e.toVertex);
    }
  }
}

int main() {
  memset(head, 0xff, sizeof(head));
  memset(queryHead, 0xff, sizeof(queryHead));

  cin >> vertexCount >> queryCount;
  int count = 0;
  for (int i = 0; i < vertexCount - 1; i++) {
    int start = 0, end = 0;
    cin >> start >> end;

    edge[count] = Edge(start, end, head[start]);
    head[start] = count;
    count++;

    edge[count] = Edge(end, start, head[end]);
    head[end] = count;
    count++;
  }

  count = 0;
  for (int i = 0; i < queryCount; i++) {
    int start = 0, end = 0;
    cin >> start >> end;

    queryEdge[count] = Edge(start, end, queryHead[start]);
    queryHead[start] = count;
    count++;

    queryEdge[count] = Edge(end, start, queryHead[end]);
    queryHead[end] = count;
    count++;
  }

  tarjan(1);

  for (int i = 0; i < queryCount; i++) {
    Edge& e = queryEdge[i * 2];
    cout << "(" << e.fromVertex << "," << e.toVertex << ") " << e.LCA << endl;
  }

  return 0;
}

用歐拉序列轉化為 RMQ 問題

定義

對一棵樹進行 DFS，無論是第一次訪問還是回溯，每次到達一個結點時都將編號記錄下來，可以得到一個長度為 \(2n-1\) 的序列，這個序列被稱作這棵樹的歐拉序列。

在下文中，把結點 \(u\) 在歐拉序列中第一次出現的位置編號記為 \(pos(u)\)（也稱作節點 \(u\) 的歐拉序），把歐拉序列本身記作 \(E[1..2n-1]\)。

過程

有了歐拉序列，LCA 問題可以在線性時間內轉化為 RMQ 問題，即 \(pos(LCA(u, v))=\min\{pos(k)|k\in E[pos(u)..pos(v)]\}\)。

這個等式不難理解：從 \(u\) 走到 \(v\) 的過程中一定會經過 \(LCA(u,v)\)，但不會經過 \(LCA(u,v)\) 的祖先。因此，從 \(u\) 走到 \(v\) 的過程中經過的歐拉序最小的結點就是 \(LCA(u, v)\)。

用 DFS 計算歐拉序列的時間複雜度是 \(O(n)\)，且歐拉序列的長度也是 \(O(n)\)，所以 LCA 問題可以在 \(O(n)\) 的時間內轉化成等規模的 RMQ 問題。

實現

參考代碼

int dfn[N << 1], pos[N], tot, st[30][(N << 1) + 2],
    rev[30][(N << 1) + 2];  // rev表示最小深度對應的節點編號

void dfs(int cur, int dep) {
  dfn[++tot] = cur;
  depth[tot] = dep;
  pos[cur] = tot;
  for (int i = head[t]; i; i = side[i].next) {
    int v = side[i].to;
    if (!pos[v]) {
      dfs(v, dep + 1);
      dfn[++tot] = cur, depth[tot] = dep;
    }
  }
}

void init() {
  for (int i = 2; i <= tot + 1; ++i)
    lg[i] = lg[i >> 1] + 1;  // 預處理 lg 代替庫函數 log2 來優化常數
  for (int i = 1; i <= tot; i++) st[0][i] = depth[i], rev[0][i] = dfn[i];
  for (int i = 1; i <= lg[tot]; i++)
    for (int j = 1; j + (1 << i) - 1 <= tot; j++)
      if (st[i - 1][j] < st[i - 1][j + (1 << i - 1)])
        st[i][j] = st[i - 1][j], rev[i][j] = rev[i - 1][j];
      else
        st[i][j] = st[i - 1][j + (1 << i - 1)],
        rev[i][j] = rev[i - 1][j + (1 << i - 1)];
}

int query(int l, int r) {
  int k = lg[r - l + 1];
  return st[k][l] < st[k][r + 1 - (1 << k)] ? rev[k][l]
                                            : rev[k][r + 1 - (1 << k)];
}

當我們需要查詢某點對 \((u, v)\) 的 LCA 時，查詢區間 \([\min\{pos[u], pos[v]\}, \max\{pos[u], pos[v]\}]\) 上最小值的所代表的節點即可。

若使用 ST 表來解決 RMQ 問題，那麼該算法不支持在線修改，預處理的時間複雜度為 \(O(n\log n)\)，每次查詢 LCA 的時間複雜度為 \(O(1)\)。

樹鏈剖分

LCA 為兩個遊標跳轉到同一條重鏈上時深度較小的那個遊標所指向的點。

樹鏈剖分的預處理時間複雜度為 \(O(n)\)，單次查詢的時間複雜度為 \(O(\log n)\)，並且常數較小。

動態樹

設連續兩次 access 操作的點分別為 u 和 v，則第二次 access 操作返回的點即為 u 和 v 的 LCA.

在無 link 和 cut 等操作的情況下，使用 link cut tree 單次查詢的時間複雜度為 \(O(\log n)\)。

標準 RMQ

前面講到了藉助歐拉序將 LCA 問題轉化為 RMQ 問題，其瓶頸在於 RMQ。如果能做到 \(O(n) \sim O(1)\) 求解 RMQ，那麼也就能做到 \(O(n) \sim O(1)\) 求解 LCA。

注意到歐拉序滿足相鄰兩數之差為 1 或者 -1，所以可以使用 \(O(n) \sim O(1)\) 的 加減 1RMQ 來做。

時間複雜度 \(O(n) \sim O(1)\)，空間複雜度 \(O(n)\)，支持在線查詢，常數較大。

例題 Luogu P3379【模板】最近公共祖先（LCA）

參考代碼

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

struct PlusMinusOneRMQ {  // RMQ
  // Copyright (C) 2018 Skqliao. All rights served.
  const static int M = 9;

  int blocklen, block, Minv[N], F[N / M * 2 + 5][M << 1], T[N], f[1 << M][M][M],
      S[N];

  void init(int n) {  // 初始化
    blocklen = std::max(1, (int)(log(n * 1.0) / log(2.0)) / 2);
    block = n / blocklen + (n % blocklen > 0);
    int total = 1 << (blocklen - 1);
    for (int i = 0; i < total; i++) {
      for (int l = 0; l < blocklen; l++) {
        f[i][l][l] = l;
        int now = 0, minv = 0;
        for (int r = l + 1; r < blocklen; r++) {
          f[i][l][r] = f[i][l][r - 1];
          if ((1 << (r - 1)) & i) {
            now++;
          } else {
            now--;
            if (now < minv) {
              minv = now;
              f[i][l][r] = r;
            }
          }
        }
      }
    }
    T[1] = 0;
    for (int i = 2; i < N; i++) {
      T[i] = T[i - 1];
      if (!(i & (i - 1))) {
        T[i]++;
      }
    }
  }

  void initmin(int a[], int n) {
    for (int i = 0; i < n; i++) {
      if (i % blocklen == 0) {
        Minv[i / blocklen] = i;
        S[i / blocklen] = 0;
      } else {
        if (a[i] < a[Minv[i / blocklen]]) {
          Minv[i / blocklen] = i;
        }
        if (a[i] > a[i - 1]) {
          S[i / blocklen] |= 1 << (i % blocklen - 1);
        }
      }
    }
    for (int i = 0; i < block; i++) {
      F[i][0] = Minv[i];
    }
    for (int j = 1; (1 << j) <= block; j++) {
      for (int i = 0; i + (1 << j) - 1 < block; i++) {
        int b1 = F[i][j - 1], b2 = F[i + (1 << (j - 1))][j - 1];
        F[i][j] = a[b1] < a[b2] ? b1 : b2;
      }
    }
  }

  int querymin(int a[], int L, int R) {
    int idl = L / blocklen, idr = R / blocklen;
    if (idl == idr)
      return idl * blocklen + f[S[idl]][L % blocklen][R % blocklen];
    else {
      int b1 = idl * blocklen + f[S[idl]][L % blocklen][blocklen - 1];
      int b2 = idr * blocklen + f[S[idr]][0][R % blocklen];
      int buf = a[b1] < a[b2] ? b1 : b2;
      int c = T[idr - idl - 1];
      if (idr - idl - 1) {
        int b1 = F[idl + 1][c];
        int b2 = F[idr - 1 - (1 << c) + 1][c];
        int b = a[b1] < a[b2] ? b1 : b2;
        return a[buf] < a[b] ? buf : b;
      }
      return buf;
    }
  }
} rmq;

int n, m, s;

struct Edge {
  int v, nxt;
} e[N * 2];

int tot, head[N];

void init(int n) {
  tot = 0;
  fill(head, head + n + 1, 0);
}

void addedge(int u, int v) {  // 加边
  ++tot;
  e[tot] = (Edge){v, head[u]};
  head[u] = tot;

  ++tot;
  e[tot] = (Edge){u, head[v]};
  head[v] = tot;
}

int dfs_clock, dfn[N * 2], dep[N * 2], st[N];

void dfs(int u, int fa, int d) {
  st[u] = dfs_clock;

  dfn[dfs_clock] = u;
  dep[dfs_clock] = d;
  ++dfs_clock;

  int v;
  for (int i = head[u]; i; i = e[i].nxt) {
    v = e[i].v;
    if (v == fa) continue;
    dfs(v, u, d + 1);
    dfn[dfs_clock] = u;
    dep[dfs_clock] = d;
    ++dfs_clock;
  }
}

void build_lca() {  // like init
  rmq.init(dfs_clock);
  rmq.initmin(dep, dfs_clock);
}

int LCA(int u, int v) {  // 求解LCA，看题解用RMQ的方法
  int l = st[u], r = st[v];
  if (l > r) swap(l, r);
  return dfn[rmq.querymin(dep, l, r)];
}

int main() {
  scanf("%d %d %d", &n, &m, &s);

  init(n);
  int u, v;
  for (int i = 1; i <= n - 1; ++i) {
    scanf("%d %d", &u, &v);
    addedge(u, v);
  }

  dfs_clock = 0;
  dfs(s, s, 0);

  build_lca();

  for (int i = 1; i <= m; ++i) {
    scanf("%d %d", &u, &v);
    printf("%d\n", LCA(u, v));
  }

  return 0;
}

習題

• 祖孫詢問
• 貨車運輸
• 點的距離

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：ouuan, Backl1ght, billchenchina, CCXXXI, ChickenHu, ChungZH, cjsoft, countercurrent-time, diauweb, Early0v0, Enter-tainer, EtaoinWu, H-J-Granger, H-Shen, Henry-ZHR, HeRaNO, hsfzLZH1, huaruoji, iamtwz, imp2002, Ir1d, kenlig, Konano, Lyccrius, Marcythm, Menci, NachtgeistW, PeterlitsZo, psz2007, shuzhouliu, SkqLiao, sshwy, SukkaW, therehello, TrisolarisHD, ttzztztz, vincent-163, WAAutoMaton, Hunter19019
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用