Lowest Common Ancestor

Definition

The Lowest Common Ancestor (LCA) of two nodes is the deepest node that is an ancestor to both.
For convenience, we denote the LCA of a node set \(S=\{v_1,v_2,\ldots,v_n\}\) as \(\text{LCA}(v_1,v_2,\ldots,v_n)\) or \(\text{LCA}(S)\).

Properties

This section is translated and adapted from wcipeg.

\(\text{LCA}(\{u\})=u\);
\(u\) is an ancestor of \(v\) if and only if \(\text{LCA}(u,v)=u\);
If \(u\) is not an ancestor of \(v\) and \(v\) is not an ancestor of \(u\), then \(u\) and \(v\) lie in different subtrees of \(\text{LCA}(u,v)\);
In preorder traversal, \(\text{LCA}(S)\) appears before all elements of \(S\), and in postorder traversal, \(\text{LCA}(S)\) appears after all elements of \(S\);
The LCA of the union of two sets is the LCA of the LCAs of each set, i.e., \(\text{LCA}(A\cup B)=\text{LCA}(\text{LCA}(A), \text{LCA}(B))\);
The LCA of two nodes must lie on the shortest path between them on the tree;
\(d(u,v)=h(u)+h(v)-2h(\text{LCA}(u,v))\), where \(d\) is the distance between two nodes on the tree, and \(h\) represents the distance from a node to the root.

Algorithms

Naive Algorithm

Process

Each time, take the node with greater depth and let it jump upward. Clearly, on the tree, these two points will eventually meet, and the meeting point is the desired LCA.
Alternatively, first adjust the deeper node upward until both have the same depth, then jump upward together. They will also eventually meet.

Properties

The naive algorithm requires a DFS of the entire tree for preprocessing, with time complexity \(O(n)\). A single query takes \(\Theta(n)\) time. If the tree has random properties, the time complexity relates to the expected height of such a random tree.

Binary Lifting

Process

Binary lifting is the classic LCA algorithm, an improvement over the naive algorithm. By preprocessing the \(\text{fa}_{x,i}\) array, the cursor can move quickly, significantly reducing the number of jumps. \(\text{fa}_{x,i}\) denotes the \(2^i\)-th ancestor of node \(x\). The \(\text{fa}_{x,i}\) array can be preprocessed via DFS.

Now, let's see how to optimize these jumps:
In the first phase of adjusting the cursors, we need to bring \(u\) and \(v\) to the same depth. We can compute the depth difference \(y\) between \(u\) and \(v\). By binary splitting \(y\), we optimize \(y\) jumps to the number of 1s in the binary representation of \(y\).
In the second phase, we try from the largest \(i\) down to \(0\) (inclusive). If \(\text{fa}_{u,i}\not=\text{fa}_{v,i}\), then set \(u\gets\text{fa}_{u,i},v\gets\text{fa}_{v,i}\). The final LCA is \(\text{fa}_{u,0}\).

Properties

The preprocessing time complexity of binary lifting is \(O(n \log n)\), and a single query takes \(O(\log n)\).
Additionally, swapping the two dimensions of the fa array to place the smaller dimension first can reduce cache misses and improve efficiency.

Example Problem

HDU 2586 How far away? Query the shortest path on a tree.

One can first compute the LCA and then use property \(7\) to answer. Alternatively, compute the result directly while finding the LCA.

Reference Code

#include <cstring>
#include <iostream>
#include <vector>

constexpr int MXN = 40005;
using namespace std;
vector<int> v[MXN];
vector<int> w[MXN];

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

// dfs, used to prepare for the lca algorithm. Accepts two parameters: the starting node of dfs and its parent node.
void dfs(int root, int fno) {
  // Initialization: the 2^0 = 1st ancestor is its parent node, and dep is one more than the parent node.
  fa[root][0] = fno;
  dep[root] = dep[fa[root][0]] + 1;
  // Initialization: other ancestor nodes: the 2^i-th ancestor node is the 2^(i-1)-th ancestor node of the 2^(i-1)-th ancestor node.
  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];
  }
  // Traverse child nodes to perform 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. Use the binary lifting algorithm to compute the lca node of x and y.
int lca(int x, int y) {
  // Ensure y is deeper than x.
  if (dep[x] > dep[y]) swap(x, y);
  // Bring y to the same depth as 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];
  // If at this point y = x, then x and y are their own ancestors.
  if (y == x) return ans;
  // Otherwise, find the first point where they are not ancestors of each other.
  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];
    }
  }
  // Return the result.
  ans += cost[x][0] + cost[y][0];
  return ans;
}

void Solve() {
  cin.tie(nullptr)->sync_with_stdio(false);
  // Initialize the ancestor array fa, cost array, and depth array dep.
  memset(fa, 0, sizeof(fa));
  memset(cost, 0, sizeof(cost));
  memset(dep, 0, sizeof(dep));
  // Read the tree: there are n nodes in total, m queries, each query finds the lca of two nodes.
  cin >> n >> m;
  // Initialize tree edges and edge weights
  for (int i = 1; i <= n; ++i) {
    v[i].clear();
    w[i].clear();
  }
  for (int i = 1; i < n; ++i) {
    cin >> a >> b >> c;
    v[a].push_back(b);
    v[b].push_back(a);
    w[a].push_back(c);
    w[b].push_back(c);
  }
  // Use dfs to prepare for lca computation.
  dfs(1, 0);
  for (int i = 0; i < m; ++i) {
    cin >> a >> b;
    cout << lca(a, b) << '\n';
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) Solve();
  return 0;
}

Tarjan's Algorithm

Process

Tarjan's algorithm is an offline algorithm that uses a Disjoint Set Union (DSU) to record the ancestor of a node. The procedure is as follows:

First, accept input edges (adjacency list) and query edges (stored in another adjacency list). Query edges are virtually added; for convenience, when inputting a query edge, add both the edge and its reverse to the queryEdge array.
Then perform a DFS traversal, using a visited array to record whether a node has been visited, and parent to record the current node's parent.
It involves the backtracking idea: when we traverse to a node, we consider its root to be itself. After the DFS rooted at this node is complete, set the node's root to its parent.
During backtracking, if for a node as the start, the other node of a queryEdge query edge has also been visited, directly update the LCA result for that query edge.
Finally, output the results.

Properties

Tarjan's algorithm requires initializing the DSU, so preprocessing takes \(O(n)\) time.

The naive Tarjan's algorithm processes all \(m\) queries in \(O(m \alpha(m+n, n) + n)\) time, but its constant factor is larger than binary lifting. There exists an \(O(m + n)\) implementation.

Note

The statement "the DSU used in the naive Tarjan LCA algorithm has special properties, making a single call to find() amortized \(O(1)\)" is incorrect.

The naive Tarjan implementation below has complexity \(O(m \alpha(m+n, n) + n)\). For a strictly linear algorithm, refer to the 1983 paper by Gabow and Tarjan, which provides an \(O(m + n)\) approach.

Implementation

Reference Code

#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) {};
};

constexpr 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;
}

Reduction to RMQ via Euler Tour Sequence

Definition

Perform a DFS on the tree. Record the node's identifier every time we visit it (whether first visit or backtrack). This yields a sequence of length \(2n-1\), called the Euler tour sequence of the tree.

Below, let \(pos(u)\) denote the position where node \(u\) first appears in the Euler sequence (also called the Euler order of node \(u\)), and denote the Euler sequence itself as \(E[1..2n-1]\).

Process

With the Euler sequence, the LCA problem can be reduced to an RMQ problem in linear time: \(pos(LCA(u, v))=\min\{pos(k)|k\in E[pos(u)..pos(v)]\}\).

This equality is intuitive: the path from \(u\) to \(v\) must pass through \(LCA(u,v)\) but not through ancestors of \(LCA(u,v)\). Therefore, the node with the smallest Euler order on the path from \(u\) to \(v\) is \(LCA(u, v)\).

Computing the Euler sequence via DFS takes \(O(n)\) time, and the Euler sequence length is also \(O(n)\). Thus, the LCA problem can be reduced to an RMQ problem of the same scale in \(O(n)\) time.

Implementation

Reference Code

int dfn[N << 1], pos[N], tot, st[30][(N << 1) + 2],
    rev[30][(N << 1) + 2];  // rev stores the node id corresponding to the minimum depth

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;  // precompute lg to replace log2 for constant optimization
  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)];
}

When we need to query the LCA of a pair \((u, v)\), query the node representing the minimum value in the interval \([\min\{pos[u], pos[v]\}, \max\{pos[u], pos[v]\}]\).

If using a Sparse Table (ST) to solve the RMQ problem, this algorithm does not support online modifications. Preprocessing takes \(O(n\log n)\) time, and each LCA query takes \(O(1)\) time.

Heavy-Light Decomposition

The LCA is the shallower of the two cursors when they jump onto the same heavy chain.

Heavy-light decomposition preprocessing takes \(O(n)\) time, and a single query takes \(O(\log n)\) time with a small constant factor.

Link Cut Tree

In a Link Cut Tree, suppose the points of two consecutive access operations are u and v. Then the point returned by the second access operation is the LCA of u and v.

Without link and cut operations, a single query using Link Cut Tree takes \(O(\log n)\) time.

Standard RMQ

As mentioned earlier, using the Euler order reduces LCA to RMQ, with the bottleneck being RMQ. If we can solve RMQ in \(O(n) \sim O(1)\), then we can solve LCA in \(O(n) \sim O(1)\).

Note that the Euler sequence satisfies that adjacent numbers differ by 1 or -1, so we can use \(O(n) \sim O(1)\) ±1 RMQ.

Time complexity \(O(n) \sim O(1)\), space complexity \(O(n)\), supports online queries, but has a large constant factor.

Example Luogu P3379【Template】Lowest Common Ancestor (LCA)

Reference Code

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

constexpr int N = 5e5 + 5;

struct PlusMinusOneRMQ {  // RMQ
  // Copyright (C) 2018 Skqliao. All rights served.
  constexpr 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) {  // Initialization
    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) {  // Add edge
  ++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) {  // Solve LCA using RMQ method
  int l = st[u], r = st[v];
  if (l > r) swap(l, r);
  return dfn[rmq.querymin(dep, l, r)];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m >> s;

  init(n);
  int u, v;
  for (int i = 1; i <= n - 1; ++i) {
    cin >> u >> v;
    addedge(u, v);
  }

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

  build_lca();

  for (int i = 1; i <= m; ++i) {
    cin >> u >> v;
    cout << LCA(u, v) << '\n';
  }

  return 0;
}

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用