guest@itl:~/home/graph$
templates/lca.cpp
compilable
$cat templates/lca

LCA — Lowest Common Ancestor

Binary lifting for LCA, distance, and k-th ancestor queries on unweighted trees in O(log n).

[Graph]|
Jul 9, 2026
|explanatory_notes.md|
#lca#binary-lifting#tree#ancestor
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
const int LOG = 18;
vector<int> adj[MAXN];
int anc[MAXN][LOG], dep[MAXN];

void dfs(int u, int p) {
    for (int v : adj[u]) {
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        anc[v][0] = u;
        for (int k = 1; k < LOG; k++)
            anc[v][k] = anc[anc[v][k-1]][k-1];
        dfs(v, u);
    }
}

int kthAncestor(int u, int k) {
    for (int i = 0; i < LOG; i++)
        if (k >> i & 1) u = anc[u][i];
    return u;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = kthAncestor(u, dep[u] - dep[v]);
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (anc[u][k] != anc[v][k])
            u = anc[u][k], v = anc[v][k];
    return anc[u][0];
}

int dist(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
38 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

LCA via Binary Lifting

Preprocess a tree in O(nlog⁡n)O(n \log n), then answer LCA queries in O(log⁡n)O(\log n).

Preprocessing

  • DFS from root to compute depths and fill ancestor table

  • anc[v][k]\text{anc}[v][k] = the 2k2^k-th ancestor of node vv

  • Recurrence: anc[v][k]=anc[anc[v][k−1]][k−1]\text{anc}[v][k] = \text{anc}[\text{anc}[v][k-1]][k-1]

    • LCA Query

  • Equalize depths by lifting the deeper node using kk-th ancestor jumps

  • Simultaneously lift both nodes from the highest bit downward until ancestors differ

  • Return anc[u][0]\text{anc}[u][0]

    • Operations

  • lca(u, v) — lowest common ancestor

  • kthAncestor(u, k) — kk-th ancestor of uu (returns −1-1 if k>k > depth)

  • dist(u, v) — tree distance: dep[u]+dep[v]−2⋅dep[lca(u,v)]\text{dep}[u] + \text{dep}[v] - 2 \cdot \text{dep}[\text{lca}(u,v)]

    • When to Use

  • LCA queries on static trees

  • Tree path distance

  • kk-th ancestor queries

  • Building block for HLD, Mo's on trees, path aggregation

    • Complexity

  • Preprocess — O(nlog⁡n)O(n \log n)

  • Query — O(log⁡n)O(\log n)

  • Space — O(nlog⁡n)O(n \log n)