Skip to content

Lowest Common Ancestor

Definition

The lowest common ancestor (LCA) of two nodes is their common ancestor farthest from the root. For convenience, we write \(\text{LCA}(v_1,v_2,\ldots,v_n)\) or \(\text{LCA}(S)\) for the lowest common ancestor of a set of nodes \(S=\{v_1,v_2,\ldots,v_n\}\).

Properties

Parts of this Properties section are translated from wcipeg, with modifications.

  1. \(\text{LCA}(\{u\})=u\);
  2. \(u\) is an ancestor of \(v\) if and only if \(\text{LCA}(u,v)=u\);
  3. if neither of \(u\) and \(v\) is an ancestor of the other, then they lie in two different subtrees of \(\text{LCA}(u,v)\);
  4. in a preorder traversal, \(\text{LCA}(S)\) comes before every element of \(S\); in a postorder traversal, it comes after all of them;
  5. the LCA of the union of two sets of nodes is the LCA of the two sets' LCAs, that is, \(\text{LCA}(A\cup B)=\text{LCA}(\text{LCA}(A), \text{LCA}(B))\);
  6. the LCA of two nodes always lies on the shortest path between them in the tree;
  7. \(d(u,v)=h(u)+h(v)-2h(\text{LCA}(u,v))\), where \(d\) is the distance between two nodes in the tree and \(h\) is the distance from a node to the root.

Algorithms

Naive algorithm

Procedure

Repeatedly take the deeper of the two nodes and move it up. Since this is a tree, the two nodes are bound to meet, and the node where they meet is the LCA. Alternatively, first move the deeper node up until the two are at the same depth, then move both up together; again they are bound to meet.

Properties

The naive algorithm preprocesses the whole tree with a DFS in \(O(n)\) time and answers a single query in \(\Theta(n)\) time. If the tree is random in some way, the running time depends on the expected height of such a random tree.

Binary lifting

Procedure

Binary lifting is the classic way to find the LCA; it improves on the naive algorithm. With a precomputed array \(\text{fa}_{x,i}\), the two pointers move quickly and make far fewer jumps. Here \(\text{fa}_{x,i}\) is the \(2^i\)-th ancestor of node \(x\); the array can be precomputed by a DFS.

Here is how the jumps are sped up: The first phase brings the two pointers \(u\) and \(v\) to the same depth. Let \(y\) be the difference between their depths. The binary decomposition of \(y\) turns the \(y\) jumps into one jump for each 1 in the binary representation of \(y\). The second phase tries each \(i\) from the largest down to \(0\) inclusive: if \(\text{fa}_{u,i}\not=\text{fa}_{v,i}\), set \(u\gets\text{fa}_{u,i},v\gets\text{fa}_{v,i}\). At the end, the LCA is \(\text{fa}_{u,0}\).

Properties

Binary lifting takes \(O(n \log n)\) time to preprocess and \(O(\log n)\) time per query. You can also swap the two dimensions of the fa array so that the smaller one comes first: this causes fewer cache misses and makes the program faster.

Example

HDU 2586 How far away? Shortest path queries on a tree.

Find the LCA first and then apply property \(7\), or compute the answer directly while finding the LCA.

Reference code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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: prepares for the lca algorithm. Takes two arguments: the node the dfs starts from and its parent.
void dfs(int root, int fno) {
  // Initialization: the 2^0 = 1st ancestor is the parent, and dep is 1 more than the parent's.
  fa[root][0] = fno;
  dep[root] = dep[fa[root][0]] + 1;
  // Initialization of the other ancestors: the 2^i-th ancestor is the
  // 2^(i-1)-th ancestor of the 2^(i-1)-th ancestor.
  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];
  }
  // Run the dfs over the children.
  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: uses binary lifting to find the lca of x and y.
int lca(int x, int y) {
  // Make y the deeper one.
  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 y = x at this point, then x and y are both their own ancestor.
  if (y == x) return ans;
  // Otherwise, find the first two nodes that are not their common ancestors.
  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, the cost array cost and the depth array dep.
  memset(fa, 0, sizeof(fa));
  memset(cost, 0, sizeof(cost));
  memset(dep, 0, sizeof(dep));
  // Read the tree: n nodes in total and m queries, each asking for the lca of two nodes.
  cin >> n >> m;
  // Initialize the 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);
  }
  // Run the dfs needed to compute the lca.
  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

Procedure

Tarjan's algorithm is an offline algorithm. It uses a disjoint set union to keep track of an ancestor of each node. It works as follows:

  1. Read the input edges into an adjacency list and the query edges into a second adjacency list. A query edge is really a virtual edge that we add; for convenience, each query edge is added to the queryEdge array together with its reverse as it is read.
  2. Run a DFS over the tree, using the visited array to record which nodes have been visited.
  3. This step relies on backtracking. When the DFS reaches a node, create a new set containing only that node. Once the DFS of the subtree rooted at one of its children has finished, merge the child's set into the current node's set and record in ancestor the shallowest node of the merged set, which is the current node.
  4. When backtracking from a node, look at each query edge in queryEdge that starts there: if its other endpoint has already been visited, the ancestor of the set containing that endpoint is the LCA of the two nodes, so store it as the LCA result of the query edge right away.
  5. Finally, output the results.

Properties

Tarjan's algorithm has to initialize the disjoint set union, so preprocessing takes \(O(n)\) time.

The naive version of Tarjan's algorithm answers all \(m\) queries in \(O(m \alpha(m+n, n) + n)\) time, but Tarjan's algorithm has a larger constant factor than binary lifting. An \(O(m + n)\) implementation exists.

Note

It is not true that the disjoint set union used in the naive Tarjan LCA algorithm is special enough for a single call to find() to take amortized \(O(1)\) time.

The naive Tarjan implementation below runs in \(O(m \alpha(m+n, n) + n)\). If you need strictly linear time, see the 1983 paper by Gabow and Tarjan, which gives an \(O(m + n)\) method.

Implementation

Reference code
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#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];
// ancestor[r]: the node of minimum depth in the set whose root is r
int parent[MAX], setSize[MAX], ancestor[MAX], visited[MAX];
int vertexCount, queryCount;

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

// Merge the sets containing x and y by size; return the root of the merged set
int unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (setSize[x] < setSize[y]) swap(x, y);
  parent[y] = x;
  setSize[x] += setSize[y];
  return x;
}

void tarjan(int u) {
  parent[u] = u;
  setSize[u] = 1;
  ancestor[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);
      // merge the subtree into the set containing u; the node of minimum depth in the merged set is still u
      ancestor[unite(u, 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 = ancestor[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 using the Euler tour

Definition

Run a DFS on a tree and write down a node's index every time the search arrives at it, whether for the first time or when backtracking. The result is a sequence of length \(2n-1\) called the Euler tour of the tree.

Below, \(pos(u)\) denotes the position of the first occurrence of node \(u\) in the Euler tour (also called the Euler tour index of \(u\)), and \(E[1..2n-1]\) denotes the Euler tour itself.

Procedure

The Euler tour reduces the LCA problem to an RMQ problem in linear time: \(pos(LCA(u, v))=\min\{pos(k)|k\in E[pos(u)..pos(v)]\}\).

The equation is easy to understand: the walk from \(u\) to \(v\) must pass through \(LCA(u,v)\) but never through any of its ancestors. So the node with the smallest Euler tour index on the walk from \(u\) to \(v\) is \(LCA(u, v)\).

A DFS computes the Euler tour in \(O(n)\) time, and the tour has length \(O(n)\), so the LCA problem reduces in \(O(n)\) time to an RMQ problem of the same size.

Implementation

Reference code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int dfn[N << 1], pos[N], tot, st[30][(N << 1) + 2],
    rev[30][(N << 1) + 2];  // rev is the index of the node with 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 instead of calling the library function log2, to reduce the constant factor
  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)];
}

To find the LCA of a pair of nodes \((u, v)\), query the range \([\min\{pos[u], pos[v]\}, \max\{pos[u], pos[v]\}]\) and take the node that its minimum corresponds to.

With a sparse table for the RMQ, the algorithm does not support online updates; preprocessing takes \(O(n\log n)\) time and each LCA query takes \(O(1)\) time.

Reduction to RMQ using the DFS order

The Euler tour has length \(2n-1\), which makes the constant factors in time and space a little large. In fact, the DFS timestamps \(\operatorname{dfn}\) are enough to find the LCA.

Consider a pair of nodes \((u,v)\) and let \(d=\operatorname{LCA}(u,v)\). If \(u=v\), then \(d=u\); this is a special case to be handled separately. Otherwise, assume without loss of generality that \(\operatorname{dfn}(u) < \operatorname{dfn}(v)\), so that \(v\) cannot be an ancestor of \(u\). Unlike the Euler tour, the DFS order does not contain \(d\) in the range \((\operatorname{dfn}(u), \operatorname{dfn}(v)]\). But the range does contain the child of \(d\) that lies on the path from \(d\) to \(v\), whether or not \(u\) is an ancestor of \(v\). So it is enough to find a node of minimum depth in the range \([\operatorname{dfn}(u) + 1, \operatorname{dfn}(v)]\) (it need not be unique): its parent is the LCA. The range starts at \(\operatorname{dfn}(u) + 1\) because, if \(u\) is an ancestor of \(v\) and the range included \(u\), the node of minimum depth would be \(u\) itself, whose parent is not the LCA.

So finding the LCA is once again an RMQ problem.

To avoid storing depths and parents separately, store \(\operatorname{fa}(u)\) at position \(\operatorname{dfn}(u)\) of the DFS order, and compare two entries of this sequence by their timestamps. The entry with the smallest timestamp in the range \([\operatorname{dfn}(u) + 1, \operatorname{dfn}(v)]\) is then \(\operatorname{LCA}(u,v)\). The reason is that every node in this range is a proper descendant of \(d\), so the DFS timestamp of its parent is at least \(\operatorname{dfn}(d)\); and the minimum \(\operatorname{dfn}(d)\) is attained at a child of \(d\) inside the range, which exists by the discussion above.

The reduction from LCA to RMQ via the DFS order takes \(O(n)\) time; the total complexity depends on the RMQ method used. Here is a reference implementation with a sparse table, with \(O(n\log n)\) preprocessing and \(O(1)\) queries:

Reference implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class LcaSolver {
  std::array<std::vector<int>, 30> mi;
  std::vector<int> dfn, log;

  auto get(int u, int v) const { return dfn[u] < dfn[v] ? u : v; }

 public:
  // Initialize.
  // n - tree size; fa - the id of parent node, 0-indexed, 0 is the root.
  LcaSolver(int n, const std::vector<int>& fa) : dfn(n), log(n + 1) {
    // Build the tree.
    std::vector<std::vector<int>> gr(n);
    for (int i = 1; i < n; ++i) gr[fa[i]].push_back(i);
    // DFS.
    auto id = 0;
    auto dfs = [&](auto&& dfs, int cr) -> void {
      dfn[cr] = id++;
      for (int nt : gr[cr]) dfs(dfs, nt);
    };
    dfs(dfs, 0);
    // Build ST table.
    for (int i = 2; i <= n; ++i) log[i] = log[i >> 1] + 1;
    mi[0].assign(n, 0);
    for (int i = 0; i < n; ++i) mi[0][dfn[i]] = fa[i];
    for (int k = 1; k <= log[n]; ++k) {
      mi[k].assign(n - (1 << k) + 1, 0);
      for (int i = 0; i + (1 << k) <= n; ++i)
        mi[k][i] = get(mi[k - 1][i], mi[k - 1][i + (1 << (k - 1))]);
    }
  }

  // Find the LCA.
  int lca(int u, int v) const {
    if (u == v) return u;
    u = dfn[u], v = dfn[v];
    if (u > v) std::swap(u, v);
    auto k = log[v - u];
    return get(mi[k][u + 1], mi[k][v - (1 << k) + 1]);
  }
};

Heavy-light decomposition

The LCA is the node at the shallower of the two pointers once both have jumped onto the same heavy path.

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

In a Link Cut Tree, if two consecutive access operations are applied to u and then to v, the node returned by the second access is the LCA of u and v.

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

Standard RMQ

The reduction from LCA to RMQ via the Euler tour was described above; its bottleneck is the RMQ. If RMQ can be solved in \(O(n) \sim O(1)\), then so can LCA.

In the Euler tour, adjacent numbers differ by 1 or -1, so the \(O(n) \sim O(1)\) ±1 RMQ applies.

This takes \(O(n) \sim O(1)\) time and \(O(n)\) space, supports online queries, and has a large constant factor.

Example: Luogu P3379 [Template] Lowest Common Ancestor (LCA)

Reference code
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#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) {  // initialize
    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 an 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) {  // find the LCA; see the solution write-up for the 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;
}

Practice problems

References