guest@cp-base:~/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
01
02
03
04
05
06
07
08
09
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
#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)