Skip to content

LCA & Tree Queries

LCA (lowest common ancestor) of two nodes in a rooted tree is the deepest node that is an ancestor of both. Used for path sums, distance on tree, and many offline queries.

Distance on a tree

If depth[v] is depth from root and lca(u,v) is known:

\[ \text{dist}(u, v) = \text{depth}[u] + \text{depth}[v] - 2\cdot\text{depth}[\text{lca}(u,v)] \]

(unweighted; for weighted, use path sums from root.)

Binary lifting LCA

Precompute up[k][v] = \(2^k\)-th ancestor of v. First DFS sets up[0] and depth; then for k from 1, fill up[k][v] = up[k-1][ up[k-1][v] ]. Query in \(O(\log n)\).

#include <vector>
using namespace std;

void dfsTree(int v, int p, const vector<vector<int>>& adj,
             vector<vector<int>>& up, vector<int>& depth) {
    up[0][v] = p;
    for (int u : adj[v])
        if (u != p) {
            depth[u] = depth[v] + 1;
            dfsTree(u, v, adj, up, depth);
        }
}

void buildBinaryLift(vector<vector<int>>& up, int LOG) {
    int n = (int)up[0].size();
    for (int k = 1; k < LOG; k++)
        for (int v = 0; v < n; v++) {
            int mid = up[k - 1][v];
            up[k][v] = (mid == -1) ? -1 : up[k - 1][mid];
        }
}

int lca(int u, int v, const vector<vector<int>>& up, const vector<int>& depth, int LOG) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != -1 && depth[up[k][u]] >= depth[v])
            u = up[k][u];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != -1 && up[k][u] != up[k][v]) {
            u = up[k][u];
            v = up[k][v];
        }
    return up[0][u];
}

Pick LOG with (1 << LOG) > n, allocate up as LOG × n filled with -1, set depth[root] = 0, call dfsTree(root, -1, adj, up, depth) then buildBinaryLift(up, LOG).

Subtree queries

Euler tour + subtree interval in DFS order, or heavy-light decomposition for path updates—see advanced data structure topics.