LCA with Binary Lifting

Quick Revisit

• USE WHEN: lowest common ancestor queries, k-th ancestor, path queries on trees
• INVARIANT: up[v][k] = 2^k-th ancestor of v; LCA found by syncing depths then jumping together
• TIME: O(N log N) preprocess, O(log N) per query | SPACE: O(N log N)
• CLASSIC BUG: off-by-one in the binary lifting table size (need ceil(log2(N)) + 1 levels)
• PRACTICE: ../12-practice-ladders/05-ladder-graphs.md

Find the lowest common ancestor of any two nodes in a rooted tree in $O(\log n)$ per query, after $O(n\log n)$ preprocessing -- using the same sparse table idea that powers RMQ, but on ancestor chains instead of arrays.

Difficulty: [Intermediate]Prerequisites: DFS and Tree DFS, Tree BasicsCF Rating: 1500-1800

---

Contents

• 2. Intuition & Concept
• 3. Visual Intuition
• 4. C++ STL Reference
• 5. Implementation (Contest-Ready)
• 6. Operations Reference
• 7. Problem Patterns & Tricks
• 8. When to Reach for This
• 9. Common Mistakes
• 10. Self-Test
• 11. Practice Problems
• 12. Further Reading

---

Intuition & Concept

Given a rooted tree, the lowest common ancestor (LCA) of nodes $u$ and $v$ is the deepest node that lies on both the path from $u$ to root and the path from $v$ to root. Equivalently, it is the node where the two paths from $u$ and $v$ to the root first meet.

The naive approach: climb from $u$ to the root, mark every node. Then climb from $v$ to the root -- the first marked node is the LCA. This costs $O(n)$ in the worst case (a bamboo / chain tree). With $q=2\times {10}^5$ queries, that is $O(nq)\approx 4\times {10}^{10}$ -- way too slow.

A slightly better naive approach: bring $u$ and $v$ to the same depth (climb the deeper one), then climb both one step at a time until they meet. Still $O(n)$ worst case.

The trick is to replace "climb one step" with "climb $2^k$ steps" -- binary lifting. Instead of parent pointers, precompute a jump table: $\text{up}[v][k]$ = the ancestor of $v$ that is $2^k$ edges above it. Any distance $d$ can be decomposed into powers of 2 (its binary representation), so you reach the ancestor at distance $d$ in $O(\log n)$ jumps.

This is the same idea behind sparse tables for RMQ: precompute answers for power-of-two ranges, then combine them. Here the "ranges" are ancestor chains.

When this appears on Codeforces: tree problems that ask for LCA directly, distance between two nodes on a tree, path queries (sum/max/min on a path), $k$-th ancestor queries, or any problem that reduces to "meet in the middle on a tree." Common CF tags: trees, binary search, dfs and similar. Typical range: 1500-2100.

Common traps at the ~1100 level:

• Forgetting to root the tree (LCA requires a rooted tree -- pick any root, usually node 1).
• Off-by-one in depth computation (root has depth 0, not 1).
• Not handling the case where $u$ is already an ancestor of $v$ (or vice versa).
• Using ${\log }_2(n)$ without +1 for the table size, causing out-of-bounds.

What the Code Won't Teach You

The two-phase LCA algorithm: equalize, then lift together.

The code runs two for loops but doesn't make clear why there are two phases or why they work together. Phase 1 equalizes depths by binary-decomposing the depth difference -- the same bit trick as kth-ancestor. Phase 2 is a greedy process: try the largest jump first, only jump when ancestors differ. When ancestors agree at jump size $2^k$, you've reached or overshot the LCA -- so you don't jump. When ancestors differ, you're still below the LCA -- so you jump. After all bits, you sit one step below the LCA. This "one step below" invariant is the most subtle part and is invisible in the code itself.

    Phase 1: Equalize Depths        Phase 2: Lift Together
    ------------------------        ----------------------

          *  (root)                       * <-- LCA
         / \                             / \
        /   \                           /   \
       +     \                         +     +  <-- u,v after loop
      / \     \     lift u            / \   / \
     /   \     |    up by 2^k       /   | |    \
    u     |    v   ---------->   (anc   (anc    (anc
    ^     |    ^                  match)  match)  match)
    |     |    |                  skip    skip    skip
    deep  |   shallow
          |                      Return up[u][0] = parent = LCA
    Bring u up to v's depth

Distance on trees via LCA.

The formula dist(u,v) = depth[u] + depth[v] - 2*depth[LCA(u,v)] seems to appear from nowhere. The insight: the unique path from $u$ to $v$ passes through the LCA. You climb from $u$ up to LCA, then descend to $v$. The climb costs depth[u] - depth[LCA] edges, the descent costs depth[v] - depth[LCA] edges, and together that gives the formula. This works for both unweighted (edge count) and weighted (prefix-sum) trees.

---

Visual Intuition

Consider this tree rooted at node 1, with 12 nodes:

                        1
                      / | \
                    2   3   4
                   / \      |
                  5   6     7
                 /|   |    / \
                8  9  10  11  12

Depths (root = 0):

    depth 0:                1
    depth 1:          2     3     4
    depth 2:        5   6         7
    depth 3:      8  9  10     11  12

Goal: Find LCA(9, 12).

Path from 9 to root: $9\to 5\to 2\to 1$ Path from 12 to root: $12\to 7\to 4\to 1$

The paths first meet at node 1. So $\text{LCA}(9,12)=1$.

Goal: Find LCA(8, 10).

Path from 8 to root: $8\to 5\to 2\to 1$ Path from 10 to root: $10\to 6\to 2\to 1$

The paths first meet at node 2. So $\text{LCA}(8,10)=2$.

The Binary Lifting Table

The whole sparse-table-on-trees idea lives in one recurrence:

$$\text{up}[v][k]=\text{up}[\text{up}[v][k-1]][k-1].$$

In words: to jump $2^k$ steps up, jump $2^{k-1}$ steps and then jump $2^{k-1}$ more. The base case is $\text{up}[v][0]=\text{parent}[v]$, which DFS hands you for free. Every column doubles the previous one.

Memorise that one line; the rest of this file is decoration on top. The visual table that follows is the recurrence executed for a 12-node tree.

For $\text{LOG}=\lfloor {\log }_2(n)\rfloor +1=4$ (since $n=12$):

    up[v][k] = 2^k-th ancestor of v  (0 if above root)

    v  | up[v][0] | up[v][1] | up[v][2] | up[v][3]
       | parent   | grandpar | 4th anc  | 8th anc
    ---+----------+----------+----------+---------
     1 |    0     |    0     |    0     |    0
     2 |    1     |    0     |    0     |    0
     3 |    1     |    0     |    0     |    0
     4 |    1     |    0     |    0     |    0
     5 |    2     |    1     |    0     |    0
     6 |    2     |    1     |    0     |    0
     7 |    4     |    1     |    0     |    0
     8 |    5     |    2     |    1     |    0
     9 |    5     |    2     |    1     |    0
    10 |    6     |    2     |    1     |    0
    11 |    7     |    4     |    1     |    0
    12 |    7     |    4     |    1     |    0

Building rule: $\text{up}[v][0]=\text{parent}[v]$, and $\text{up}[v][k]=\text{up}[\text{up}[v][k-1]][k-1]$.

The second column doubles the first: to jump $2^1=2$ steps, jump $2^0$ twice. To jump $2^2=4$ steps, jump $2^1$ twice. Each column is built from the previous one.

Binary Lifting Table -- Step-by-Step Construction

Follow how up[v][0], up[v][1], and up[v][2] are built for nodes 8, 9, 10:

    Tree (rooted at 1):

              1            depth 0
            / | \
          2   3   4        depth 1
         / \      |
        5   6     7        depth 2
       /|   |    / \
      8  9  10  11  12     depth 3

    === Step 0: up[v][0] = parent  (base case from DFS) ===

      up[8][0]  = 5          8 ---> 5
      up[9][0]  = 5          9 ---> 5
      up[10][0] = 6         10 ---> 6

    === Step 1: up[v][1] = up[ up[v][0] ][0]  (grandparent) ===

      up[8][1]  = up[ up[8][0] ][0]
                = up[  5  ][0]
                = 2              8 ---> 5 ---> 2
                                 \____2^1____/

      up[9][1]  = up[5][0] = 2          9 ---> 5 ---> 2
      up[10][1] = up[6][0] = 2         10 ---> 6 ---> 2

    === Step 2: up[v][2] = up[ up[v][1] ][1]  (4th ancestor) ===

      up[8][2]  = up[ up[8][1] ][1]
                = up[  2  ][1]
                = 0 (sentinel)   8 --> 5 --> 2 --> 1 --> *
                                 \________2^2________/
                                 (above root = sentinel 0)

      up[9][2]  = up[2][1] = 0  (same: 4th ancestor above root)
      up[10][2] = up[2][1] = 0

    Key: each column k uses column k-1 TWICE.
         Loop order MUST be: k outer (1..LOG), v inner (all nodes).

LCA Query Walkthrough: LCA(9, 10)

    Step 0: u=9 (depth 3), v=10 (depth 3)
            Depths are equal, skip the leveling step.

                        1
                      / | \
                    2   3   4         u and v are
                   / \      |         at depth 3
                  5   6     7
                 /|   |
              ->8  9  10<-
                  u=9  v=10

Step 1: Both at depth 3, same depth. Check if $u=v$: no ($9\ne 10$). Now jump both up simultaneously using binary lifting. Start from the highest power $k$ and go down:

• $k=3$: $\text{up}[9][3]=0$, $\text{up}[10][3]=0$. Equal (both 0). Skip -- jumping this far overshoots.
• $k=2$: $\text{up}[9][2]=1$, $\text{up}[10][2]=1$. Equal. Skip -- we'd land on the LCA or above it.
• $k=1$: $\text{up}[9][1]=2$, $\text{up}[10][1]=2$. Equal. Skip.
• $k=0$: $\text{up}[9][0]=5$, $\text{up}[10][0]=6$. Not equal! Jump: $u=5$, $v=6$.

                        1
                      / | \
                    2   3   4
                   / \      |
                ->5   6<-   7      u=5, v=6
                 /|   |
                8  9  10

No more powers to try. The LCA is $\text{parent}(u)=\text{parent}(5)=2$.

LCA Query Walkthrough: LCA(9, 12)

    Step 0: u=9 (depth 3), v=12 (depth 3)
            Same depth. Check u == v? No.

    Binary search phase:
      k=3: up[9][3]=0, up[12][3]=0  -> equal, skip
      k=2: up[9][2]=1, up[12][2]=1  -> equal, skip
      k=1: up[9][1]=2, up[12][1]=4  -> NOT equal! Jump.
            u = 2, v = 4

                        1
                      / | \
                  ->2   3   4<-     u=2, v=4
                   / \      |
                  5   6     7
                 /|   |    / \
                8  9  10  11  12

      k=0: up[2][0]=1, up[4][0]=1  -> equal, skip

    Answer: parent(u) = parent(2) = 1

When Depths Differ: LCA(8, 7)

$u=8$ at depth 3, $v=7$ at depth 2. First bring them to the same depth by lifting the deeper node.

Depth difference = $3-2=1$. In binary, $1=(1{)}_2$. Jump $u$ by $2^0=1$:

    Before:                         After leveling:

         1                               1
       / | \                            / | \
     2   3   4                        2   3   4
    / \      |                       / \      |
   5   6     7 <-- v=7            ->5   6     7<- v=7
  /|   |                            u=5
 8  9  10
 ^-- u=8

Now $u=5$ (depth 2), $v=7$ (depth 2). Proceed with the binary search phase:

• $k=1$: $\text{up}[5][1]=1$, $\text{up}[7][1]=1$. Equal, skip.
• $k=0$: $\text{up}[5][0]=2$, $\text{up}[7][0]=4$. Not equal! Jump: $u=2$, $v=4$.

Answer: $\text{parent}(2)=1$.

LCA Query Execution -- Phase-by-Phase Diagram

A complete trace of LCA(8, 11) showing both phases and node positions at each step:

    Tree:         1  (depth 0)
                / | \
              2   3   4  (depth 1)
             / \      |
            5   6     7  (depth 2)
           /|   |    / \
          8  9  10  11  12  (depth 3)

    Query: LCA(8, 11)
    depth[8] = 3, depth[11] = 3

    +----- PHASE 1: Equalize Depths ------+
    |                                      |
    |  diff = 3 - 3 = 0                   |
    |  No lifting needed.                 |
    |  u = 8, v = 11 (both at depth 3)   |
    |                                      |
    +--------------------------------------+

    +----- PHASE 2: Lift Together ---------+
    |                                      |
    |  Check u == v?  8 != 11  -> continue |
    |                                      |
    |  k=3: up[8][3]=0  up[11][3]=0       |
    |        equal -> skip                 |
    |                                      |
    |  k=2: up[8][2]=0  up[11][2]=0       |
    |        equal -> skip                 |
    |                                      |
    |  k=1: up[8][1]=2  up[11][1]=4       |
    |        DIFFER -> JUMP!              |
    |        u = 2, v = 4                  |
    |                                      |
    |         1  <-- LCA is here           |
    |       / | \                          |
    |    ->2   3   4<-   (u=2, v=4)       |
    |     / \      |                       |
    |    5   6     7                       |
    |                                      |
    |  k=0: up[2][0]=1  up[4][0]=1        |
    |        equal -> skip                 |
    |                                      |
    |  Loop ends. Return up[u][0]          |
    |  = up[2][0] = 1                      |
    +--------------------------------------+

    Result: LCA(8, 11) = 1  #

Tree Distance via LCA -- Visual

The distance formula dist(u,v) = depth[u] + depth[v] - 2*depth[LCA] counts edges on the unique path:

    Find dist(9, 11):
    LCA(9, 11) = 1

              1  <---+ LCA      depth = 0
            / | \    |
          2   3   4  |          depth = 1
         / \      |  |
        5   6     7  |          depth = 2
       /|   |    / \
      8  9  10  11  12          depth = 3
         ^       ^
         u       v

    Path: 9 -> 5 -> 2 -> 1 -> 4 -> 7 -> 11
           \___climb___/   \___descend__/
            3 - 0 = 3        3 - 0 = 3
            edges up          edges down

    dist = depth[9] + depth[11] - 2 * depth[LCA(9,11)]
         = 3        + 3         - 2 * 0
         = 6 edges

    +-------------------------------------------+
    |  General formula:                         |
    |                                           |
    |      u              v                     |
    |       \            /                      |
    |    (depth[u]    (depth[v]                 |
    |     - depth[L])  - depth[L])              |
    |         \        /                        |
    |          +--L--+    L = LCA(u,v)          |
    |                                           |
    |  dist = (depth[u]-depth[L])               |
    |       + (depth[v]-depth[L])               |
    |       = depth[u]+depth[v] - 2*depth[L]    |
    +-------------------------------------------+

---

C++ STL Reference

Binary lifting is a manual data structure -- no STL container does it for you. But these STL utilities help:

Function / Class	Header	What it does	Time Complexity
vector<vector<int>>	<vector>	Adjacency list for the tree	--
__lg(n)	built-in	$\lfloor {\log }_2(n)\rfloor$ for positive $n$	$O(1)$
__builtin_clz(n)	built-in	Count leading zeros, gives $\lfloor {\log }_2(n)\rfloor =31-\text{clz}(n)$	$O(1)$
bit_width(unsigned n)	<bit> (C++20)	$\lfloor {\log }_2(n)\rfloor +1$	$O(1)$
swap(a, b)	<utility>	Swap two values	$O(1)$

---

Implementation (Contest-Ready)

Minimal Template

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005, LOG = 18;
int up[MAXN][LOG], dep[MAXN];
vector<int> adj[MAXN];

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1, 0, 0);
    while (q--) {
        int u, v; cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
}

Explained Version

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int LOG = 18;  // 2^17 = 131072 > 200000, so 18 levels suffice

// up[v][k] = the 2^k-th ancestor of v. up[v][0] = parent(v).
// If v has no such ancestor (above root), up[v][k] = 0.
// We use 0 as a sentinel: node numbering is 1-based, and up[0][k] = 0 for all k.
int up[MAXN][LOG];
int dep[MAXN];          // depth of each node (root = depth 0)
vector<int> adj[MAXN];  // adjacency list

void dfs(int v, int parent, int depth) {
    up[v][0] = parent;
    dep[v] = depth;

    // Build the jump table for v.
    // up[v][k] = up[ up[v][k-1] ][k-1]
    // "To go 2^k steps up, first go 2^(k-1) steps, then another 2^(k-1) steps."
    for (int k = 1; k < LOG; k++)
        up[v][k] = up[up[v][k-1]][k-1];

    for (int u : adj[v])
        if (u != parent)
            dfs(u, v, depth + 1);
}

int lca(int u, int v) {
    // Phase 1: Bring u and v to the same depth.
    // Ensure u is the deeper node.
    if (dep[u] < dep[v]) swap(u, v);

    int diff = dep[u] - dep[v];
    // Lift u by 'diff' steps. Decompose diff into powers of 2.
    // If bit k is set in diff, jump u by 2^k.
    for (int k = 0; k < LOG; k++)
        if ((diff >> k) & 1)
            u = up[u][k];

    // Phase 2: If u == v after leveling, v was an ancestor of the original u.
    if (u == v) return u;

    // Phase 3: Binary search for LCA.
    // Try jumping both u and v by 2^k, from largest k down to 0.
    // If up[u][k] == up[v][k], the jump lands on or above the LCA -- don't take it.
    // If up[u][k] != up[v][k], the jump lands below the LCA -- take it.
    // After the loop, u and v are the children of the LCA.
    for (int k = LOG - 1; k >= 0; k--)
        if (up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }

    // u and v are now direct children of the LCA.
    return up[u][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    // Root the tree at node 1. Node 0 is a sentinel (non-existent).
    dfs(1, 0, 0);

    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
}

k-th Ancestor Query

A direct application of the jump table. To find the $k$-th ancestor of node $v$, decompose $k$ into powers of 2 and jump:

int kth_ancestor(int v, int k) {
    for (int j = 0; j < LOG; j++)
        if ((k >> j) & 1) {
            v = up[v][j];
            if (v == 0) return -1;  // no such ancestor
        }
    return v;
}

Distance Between Two Nodes

Any path between $u$ and $v$ passes through $\text{LCA}(u,v)$. The distance is:

$$\text{dist}(u,v)=\text{dep}[u]+\text{dep}[v]-2\cdot \text{dep}[\text{LCA}(u,v)]$$

int dist(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

---

Operations Reference

Operation	Time	Space
Preprocessing (DFS + table)	$O(n\log n)$	$O(n\log n)$
LCA query	$O(\log n)$	$O(1)$
$k$-th ancestor query	$O(\log n)$	$O(1)$
Distance query	$O(\log n)$	$O(1)$
Path aggregate (with stored values)	$O(\log n)$	$O(n\log n)$
Total space for jump table	--	$O(n\log n)$

For $n=2\times {10}^5$: table size = $200000\times 18\times 4$ bytes $\approx 14$ MB. Fits in 256 MB.

---

Problem Patterns & Tricks

Pattern 1: Distance on a Tree

Given a weighted tree, find the distance between two nodes. Store prefix sums from root: $\text{dist\_root}[v]$ = weighted distance from root to $v$. Then $\text{dist}(u,v)=\text{dist\_root}[u]+\text{dist\_root}[v]-2\cdot \text{dist\_root}[\text{LCA}(u,v)]$.

This pattern is extremely common. Almost any "path query" on a tree reduces to LCA.

Problems: CSES Distance Queries (1135), CF 519E

Pattern 2: Path Aggregate Queries (Max/Min/Sum on Path)

Store aggregate values in the jump table. For example, for path maximum:

int mx[MAXN][LOG];  // mx[v][k] = max edge weight on the path from v to up[v][k]

// In DFS:
mx[v][0] = weight_to_parent[v];
for (int k = 1; k < LOG; k++) {
    up[v][k] = up[up[v][k-1]][k-1];
    mx[v][k] = max(mx[v][k-1], mx[up[v][k-1]][k-1]);
}

To answer a path query, combine aggregates from both sides during the LCA climb. This gives $O(\log n)$ per query without any heavy data structures.

Problems: CF 609E (Minimum spanning tree + path max), CF 1702G2

Pattern 3: k-th Ancestor (Functional Graph Successor)

"Given a functional graph (each node has exactly one outgoing edge), find the node reached after $k$ steps from $v$." This is exactly the $k$-th ancestor / $k$-th successor problem. Build the same binary lifting table over the functional graph.

Functional graphs appear in problems about repeated transformations: applying a function $k$ times, finding cycle entry points, etc.

Problems: CSES Company Queries I (1687), CSES Planets Queries I (1750)

Pattern 4: LCA-based Subtree / Path Counting

"How many nodes on the path from $u$ to $v$?" Answer: $\text{dep}[u]+\text{dep}[v]-2\cdot \text{dep}[\text{LCA}(u,v)]+1$.

"Does node $w$ lie on the path from $u$ to $v$?" Check: $\text{dist}(u,w)+\text{dist}(w,v)=\text{dist}(u,v)$.

These simple reductions come up in path-intersection and path-counting problems.

Problems: CF 1328E, CF 208E

Pattern 5: Virtual Tree (Auxiliary Tree)

When a query involves a small subset $S$ of nodes ($|S|\ll n$), build a virtual tree containing only the nodes in $S$ and their pairwise LCAs. The virtual tree has $O(|S|)$ nodes and preserves all path relationships. Binary lifting is used to compute the LCAs needed to build it.

Sort $S$ by Euler tour order, then compute LCA of consecutive pairs -- the set of LCA values plus $S$ itself gives the virtual tree nodes.

Problems: CF 613D, CF 1083A

Pattern 6: Binary Search on Ancestors

"Find the highest ancestor of $v$ satisfying some property $P$." Binary lifting naturally supports this: try jumping $2^k$ from largest $k$ down. If the ancestor $2^k$ steps up satisfies $P$, jump; otherwise, don't. After the loop, you are at the answer (or one step below).

int highest_ancestor_with_property(int v) {
    for (int k = LOG - 1; k >= 0; k--)
        if (up[v][k] != 0 && property(up[v][k]))
            v = up[v][k];
    return v;
}

Problems: CF 1328E, CF 1702G2

---

8. When to Reach for This

Binary lifting LCA is your go-to tool when the problem involves any of: LCA queries on a static rooted tree, k-th ancestor lookups, distance between tree nodes, or aggregating values (sum/max/min) along a root-to-node path. It also applies to functional graphs (each node has one successor) where you need the k-th successor.

Related topics:

• Preprocessing step: DFS / Tree DFS
• Alternative O(1)-query LCA: Euler tour + sparse table (see also data structures -- sparse table)
• Tree input handling: Graph representation
• Practice: Graph practice ladder

Contest Cheat Sheet

+-----------------------------------------------------------+
|  LCA WITH BINARY LIFTING  --  Quick Reference             |
+-----------------------------------------------------------+
|                                                           |
|  WHEN TO USE:                                             |
|    - LCA of two nodes in a tree                           |
|    - k-th ancestor queries                                |
|    - Distance / path queries on trees                     |
|    - k-th successor in functional graphs                  |
|                                                           |
|  SETUP:                                                   |
|    LOG = 18 (for n <= 2e5), 20 (for n <= 1e6)            |
|    up[v][0] = parent[v]                                   |
|    up[v][k] = up[up[v][k-1]][k-1]                         |
|    Build during DFS.  Node 0 = sentinel.                  |
|                                                           |
|  LCA(u, v):                                               |
|    1. Bring deeper node up to same depth (bit jumps)      |
|    2. If equal, done                                      |
|    3. Jump both from k=LOG-1 down to 0:                   |
|       if up[u][k] != up[v][k]: jump both                  |
|    4. Answer = up[u][0]                                   |
|                                                           |
|  COMPLEXITY:  O(n log n) build, O(log n) query            |
|  SPACE:       O(n log n) ~ 14 MB for n=2e5               |
|                                                           |
|  DIST(u,v) = dep[u] + dep[v] - 2*dep[lca(u,v)]           |
+-----------------------------------------------------------+

---

Common Mistakes

Sentinel node 0. The entire technique relies on up[0][k] = 0 for all $k$. Use 1-based node indexing and never assign a real node the index 0. If you use 0-based indexing, use $-1$ as sentinel and be careful with array access.

LOG value too small. If $\text{LOG}<\lfloor {\log }_2(n)\rfloor +1$, the table is incomplete and queries on deep nodes give wrong answers. For $n\le 2\times {10}^5$, use LOG = 18. For $n\le {10}^6$, use LOG = 20. Safe formula: LOG = __lg(n) + 2.

Stack overflow on deep trees. A chain tree (bamboo) of $n=2\times {10}^5$ nodes causes DFS recursion depth of $2\times {10}^5$. Default stack size on many systems is ~1 MB (~250k frames for simple DFS). Solutions:

• Iterative DFS (recommended for contests):

void bfs_build(int root) {
    queue<int> q;
    q.push(root);
    dep[root] = 0;
    up[root][0] = 0;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int k = 1; k < LOG; k++)
            up[v][k] = up[up[v][k-1]][k-1];
        for (int u : adj[v]) {
            if (u == up[v][0]) continue;
            up[u][0] = v;
            dep[u] = dep[v] + 1;
            q.push(u);
        }
    }
}

• Or increase stack size with ulimit -s unlimited on Linux (not available on all judges).

Forgetting the u == v check after leveling. If $u$ is an ancestor of $v$ (or vice versa), after bringing them to the same depth, $u=v$. If you skip this check and proceed to the binary search phase, you return up[u][0] -- the parent of the LCA, which is wrong.

Depth off-by-one. Root should be depth 0. If root is depth 1, the depth difference calculation still works, but dep values differ by 1 from what you might expect in distance formulas.

Skipping the depth-equalization phase. Forgetting to lift both nodes to the same depth before the main binary-search loop is a subtle bug. The Phase 2 loop assumes dep[u] == dep[v]; if they differ, the ancestors at each power-of-two level are incomparable and the loop produces garbage.

Querying with invalid nodes. If $u$ or $v$ is 0 or out of bounds, you get garbage. Always validate input in interactive problems.

Building table before DFS is complete. The table for node $v$ must be built after the table for $\text{parent}(v)$ is built. DFS naturally ensures this (parent is visited first). BFS also works (process level by level).

Mental Traps

Trap: "The loop order for building the table doesn't matter."

The recurrence up[v][k] = up[up[v][k-1]][k-1] reads from column k-1 to fill column k. When building in a separate loop (not during DFS), the outer loop must be over k. If you swap the loops (v outer, k inner), you may read up[w][k-1] for a node w whose column k-1 isn't filled yet:

    CORRECT (k outer, v inner):       WRONG (v outer, k inner):

    for k = 1..LOG:                   for v = 1..n:
      for v = 1..n:                     for k = 1..LOG:
        up[v][k] = ...                    up[v][k] = ...

       k=0  k=1  k=2                    k=0  k=1  k=2
    v +----+----+----+                v +----+----+----+
    1 | ok | ok | ok |                1 | ok | ok | ok |
    2 | ok | ok | ok |                2 | ok | ok | ok |
    3 | ok | ok | ok |                3 | ok | ??<-------- reads
    4 | ok | ok | ok |                4 | -- | -- | --    up[w][k-1]
    5 | ok | ok | ok |                5 | -- | -- | --    for w = 4
      +----+----+----+                  +----+----+----+  but row 4
    Fills column-by-column:           not filled yet!
    all k=0, then all k=1...          Row-by-row: BROKEN

Trap: "LOG = 15 is enough for n = 100,000."

$2^{15}=32768<{10}^5$. The table can't reach the root for nodes deeper than 32768. Queries silently return wrong LCA values -- they pass small tests but fail on chains:

    n = 100000, LOG = 15

    Chain tree:  1 -- 2 -- 3 -- ... -- 100000

    Node 100000 at depth 99999.
    Max reachable ancestor: 2^15 - 1 = 32767 steps up
                            = node 100000 - 32767 = node 67233

    +-- depth 0 --------> node 1 (root)
    |                       ^
    |   UNREACHABLE         | can't reach
    |   by binary lifting   |
    +-- depth 67233 ------> node 67233
    |                       ^
    |   REACHABLE           | max jump = 2^15
    |                       |
    +-- depth 99999 ------> node 100000
                            v query starts here

    Fix: LOG = 17  (2^17 = 131072 > 100000)
         or LOG = __lg(n) + 2 for safety

Trap: "After Phase 2, u is the LCA."

Phase 2 lifts u and v as long as their ancestors differ. The moment ancestors agree, you don't jump -- leaving u and v one step below the LCA. The answer is up[u][0] (the parent), not u:

    Phase 2 ends with u and v ONE STEP BELOW LCA:

              * <-- LCA = up[u][0]   <-- RETURN THIS
             / \
            /   \
           u     v   <-- u and v land here
                         (children of LCA)

    WHY one step below?
    +--------------------------------------------------+
    | k=2: up[u][2] == up[v][2]  -> DON'T jump         |
    |       (would land ON or ABOVE LCA)               |
    | k=1: up[u][1] == up[v][1]  -> DON'T jump         |
    | k=0: up[u][0] != up[v][0]  -> JUMP!              |
    |       u = up[u][0], v = up[v][0]                 |
    |       (still BELOW LCA)                          |
    +--------------------------------------------------+
    | After loop: u,v are children of LCA              |
    | Return up[u][0]  (NOT u!)                        |
    +--------------------------------------------------+

    Common bug: returning u instead of up[u][0]
    gives the CHILD of the LCA -- wrong by one level.

---

Self-Test

Before moving on, verify you can do each of these without looking at the code above:

• [ ] Build the binary lifting table from memory -- write the loop order (k outer, v inner or during DFS), the base case up[v][0] = parent[v], and the recurrence up[v][k] = up[up[v][k-1]][k-1].
• [ ] Implement the two-phase LCA query -- Phase 1 (equalize depths via bit decomposition) and Phase 2 (lift both from k=LOG-1 down to 0, jumping only when ancestors differ) -- and explain why the return value is up[u][0], not u.
• [ ] Compute tree distance using the formula dist(u,v) = dep[u] + dep[v] - 2*dep[LCA(u,v)] and explain why it works (path goes up to LCA then down).
• [ ] State the correct LOG value for $n={10}^5$ (LOG = 17) and $n=2\times {10}^5$ (LOG = 18), and explain why "too small" causes silent wrong answers on deep trees.
• [ ] Write the k-th ancestor query -- decompose $k$ into powers of 2 and jump, handling the case where the ancestor doesn't exist.
• [ ] Explain the "one step below" invariant -- why Phase 2's greedy loop (skip when ancestors agree, jump when they differ) leaves u and v as children of the LCA.
• [ ] Identify when to use binary lifting vs Euler Tour + RMQ -- binary lifting is simpler and supports k-th ancestor / path aggregates; Euler Tour + Sparse Table gives $O(1)$ queries but is less versatile.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Company Queries I	CSES 1687	Easy	Pure $k$-th ancestor, direct binary lifting
2	Company Queries II	CSES 1688	Easy	Standard LCA query
3	Distance Queries	CSES 1135	Easy	$\text{dist}(u,v)$ via LCA and depths
4	Planets Queries I	CSES 1750	Easy	Binary lifting on a functional graph
5	CF 519E	CF	1800	LCA + counting nodes in a subtree
6	CF 609E	CF	2100	MST + path max with binary lifting
7	CF 1328E	CF	1600	Check if nodes form a vertical path using LCA
8	CF 208E	CF	2100	$k$-th ancestor + Euler tour + offline counting
9	Counting Paths	CSES 1136	Medium	LCA + difference array on tree paths
10	CF 1702G2	CF	2100	Path intersections via LCA

---

Rating Progression

CF Rating	What You Should Be Comfortable With
1200	Basic tree traversal, finding depth, naive LCA with parent pointers
1500	Binary lifting LCA template, $k$-th ancestor, distance between tree nodes
1800	Path aggregates (max, min, GCD on paths), LCA + difference arrays for path updates, virtual tree
2100	LCA in HLD context, persistent binary lifting, LCA-based MST verification, weighted binary lifting for complex path queries

Debug Exercises

Bug 1: Binary lifting table has wrong values:

up[v][0] = parent[v];
for (int j = 1; j < LOG; j++)
    for (int v = 1; v <= n; v++)
        up[v][j] = up[up[v][j-1]][j-1];

Answer

The loop order is correct (j outer, v inner), and the recurrence up[v][j] = up[up[v][j-1]][j-1] is correct. If values are still wrong, the issue is likely that parent[v] (i.e., up[v][0]) was not correctly computed during the DFS. Verify that the DFS correctly sets parent[v] for all nodes.

Bug 2: LCA gives wrong result for nodes at the same depth:

// After equalizing depths:
if (u == v) return u;
for (int j = LOG - 1; j >= 0; j--) {
    if (up[u][j] != up[v][j]) {
        u = up[u][j];
        v = up[v][j];
    }
}
return u;  // BUG: should return up[u][0]

Answer

After the binary search loop, u and v are the children of the LCA (the loop stops when the ancestors are the same, meaning one more jump would overshoot). The LCA is up[u][0], not u. Fix: return up[u][0].

Bug 3: $k$-th ancestor returns wrong node for large $k$:

int kth_ancestor(int v, int k) {
    for (int j = 0; j < LOG; j++) {
        if (k & (1 << j)) {
            v = up[v][j];
        }
    }
    return v;
}
// Returns wrong answer when k > depth[v]

Answer

When $k>\text{depth}[v]$, the node doesn't have a $k$-th ancestor (you'd go above the root). The function jumps to invalid nodes without checking. Fix: if k > depth[v], return -1 (or handle as "doesn't exist"). Also ensure up[root][j] = root for all $j$ so that jumping above the root stays at root rather than accessing garbage memory.

Historical Note

Binary lifting for LCA was popularized by Bender and Farach-Colton (2000), though the technique of precomputing power-of-2 ancestors was known earlier. The Euler Tour + RMQ reduction for $O(1)$ LCA was formalized in the same paper, establishing the theoretical optimality of LCA queries.

---

Further Reading

• cp-algorithms: LCA with Binary Lifting -- the standard reference, includes proof of correctness.
• cp-algorithms: LCA with Euler Tour + Sparse Table -- the $O(1)$ per query alternative.
• Codeforces Blog: Binary Lifting Tutorial -- community tutorial with practice links.

Binary Lifting vs Euler Tour + RMQ: Both achieve $O(n\log n)$ preprocessing. Binary lifting gives $O(\log n)$ per query; Euler Tour + Sparse Table gives $O(1)$ per query. In practice, binary lifting is:

• Simpler to code (no Euler tour flattening, no RMQ structure).
• More versatile (supports $k$-th ancestor, path aggregates in the same table).
• The $O(\log n)$ per query is fast enough for almost all contest constraints ($n,q\le 2\times {10}^5$, so $\log n\approx 18$).

Use Euler Tour + RMQ when you need $O(1)$ queries and can afford the extra implementation complexity, or when $q$ is very large relative to $n$.

For heavier path queries (path updates + queries), consider Heavy-Light Decomposition or Euler Tour + Segment Tree.

Dynamic trees. Binary lifting is a static structure -- it cannot handle edge insertions or deletions. For dynamic LCA, look into Link-Cut Trees (Splay-based, $O(\log n)$ amortized per operation) or Euler Tour Trees.

---

Recap

Binary lifting is repeated squaring for trees: precompute $\text{up}[v][k]$ (the $2^k$-th ancestor of $v$) so that any jump of $d$ steps decomposes into $O(\log n)$ power-of-two hops.

1. Build the jump table during DFS: up[v][0] = parent, up[v][k] = up[up[v][k-1]][k-1]. Loop order matters -- k outer, v inner (or fill during DFS).
2. LCA query in two phases: equalize depths by lifting the deeper node, then lift both nodes in sync from k = LOG-1 down to 0, jumping only when ancestors differ. After the loop, up[u][0] is the LCA.
3. Extensions fall out naturally: k-th ancestor (decompose k into bits), tree distance (dep[u] + dep[v] - 2*dep[LCA]), path aggregates (store max/min/sum alongside the jump table).

"Powers of two let you climb any height."