LCA, Binary Lifting & Euler Tour
The lowest common ancestor (LCA) of two nodes and in a rooted tree is the deepest node that is an ancestor of both (a node counts as its own ancestor). It is the meeting point of the two root-ward paths, and once you can find it quickly, a whole family of tree questions becomes arithmetic: the distance between two nodes, the sum or maximum on the path between them, whether one node lies on the path between two others, the -th node on a path.
This lesson builds three LCA algorithms, each better for a different situation: binary lifting ( preprocessing, per query, and the jump-pointer table answers -th-ancestor queries too), the Euler tour plus sparse table ( preprocessing, per query), and Tarjan's offline algorithm with a disjoint-set union ( when all queries are known in advance). Along the way you will learn the single most useful trick for trees with updates: flattening the tree with entry/exit times so that every subtree is a contiguous range of an array, which lets a Fenwick tree or segment tree answer subtree queries directly.
Why this exists
Trees are everywhere — file systems, DOM documents, organisational charts, phylogenies, parse trees, routing trees, version histories — and "where do these two paths meet?" is one of the most common questions asked of them. Walking up from both nodes answers it in time proportional to the depth, which is fine for balanced trees and terrible for a chain of nodes queried times ( steps).
The theory of fast LCA is old and deep. Aho, Hopcroft and Ullman studied offline LCA in 1973; Tarjan's 1979 paper "Applications of path compression on balanced trees" gave the offline union-find algorithm still taught today. Harel and Tarjan (1984) were the first to achieve preprocessing and query online, with a famously intricate construction; Schieber and Vishkin (1988) simplified it; and Bender and Farach-Colton (2000) gave the clean reduction most people now learn: LCA reduces to range-minimum query over an Euler tour, and RMQ can be solved with a sparse table. The jump pointer idea behind binary lifting appears in the level-ancestor literature (Berkman and Vishkin 1994; Bender and Farach-Colton's "The Level Ancestor Problem Simplified", 2004) and is the most widely implemented method in practice because it is short, general and extends to path aggregates.
Binary lifting is also bigger than trees. Any functional graph — a function from a finite set to itself, where every node has exactly one successor — supports "where am I after steps?" in with the same doubling table. Bitcoin Core uses a version of this idea: each block index stores a pskip pointer to an earlier ancestor chosen so that GetAncestor(height) runs in logarithmic time along a chain of hundreds of thousands of blocks.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "lowest / nearest common ancestor", "meeting point", "common boss" | LCA (binary lifting, or Euler tour + RMQ) |
| "distance between and in a tree", many queries | |
| "-th ancestor", "boss levels up", "the node steps along the path" | Binary lifting jump table |
| "sum / xor of values on the path –", static values | Root prefix sums + LCA |
| "max / min edge on the path –", static | Binary lifting with a max stored per jump |
| "add to every node on the path –", read results at the end | Difference on tree: at , ; at lca and its parent; subtree sums |
| "subtree sum / count / max with updates" | Flatten with tin/tout, Fenwick or segment tree over positions |
| "is an ancestor of ?", "is on the path –?" | |
| "where after steps", "teleporters", "each node has one successor", up to | Binary lifting on a functional graph |
| all LCA queries known in advance, tight memory | Tarjan's offline LCA with DSU |
| path updates and path queries, both dynamic | Not enough: Heavy-Light Decomposition |
The literal words: ancestor, path between, distance in a tree, subtree, steps, boss / manager / parent of parent.
Intuition & first principles
Naive LCA: equalise depths, then climb together
Compute every node's parent and depth with one BFS or DFS from the root. To find : while is deeper than , replace by its parent; likewise for ; now both are at the same depth, and while , move both up one step. They meet exactly at the LCA, because two nodes at the same depth have their common ancestors at the same heights above them.
That is per query, where is the tree height: on a balanced tree, on a path. The question is how to move up many levels at once.
Doubling: jump by powers of two
Any distance is a sum of distinct powers of two (its binary representation). If every node knows its st, nd, th, th, … ancestor, then "go up levels" is at most jumps: for each set bit of , jump . And the table is easy to fill, because the -th ancestor is the -th ancestor of the -th ancestor:
This is the same doubling recurrence as the sparse table in the previous lesson; the "array" is now each node's path to the root.
Finding the LCA with jumps uses a slightly subtler idea. After equalising depths, we want the highest pair of ancestors at the same height with ; their common parent is the LCA. "Is after jumping levels?" is a monotone predicate in : true for small (below the LCA the paths are disjoint), false for at or above the LCA. So we binary search on using the powers of two from largest to smallest: try to jump ; if the two ancestors would differ, jump (we are still below the LCA); if they would coincide, do not (we might overshoot). This is binary search over a monotone predicate, written in the "build the answer bit by bit" style. When it finishes, and are distinct children of the LCA.
Flattening: the Euler tour
Run a DFS and record a timestamp tin[v] when you enter and tout[v] when you leave it (with a counter that increases only on entry, tout[v] is the largest tin in 's subtree). The DFS visits all of 's subtree between entering and leaving , so
- the subtree of is exactly the set of nodes with in — a contiguous range;
- is an ancestor of iff .
Lay node values out in an array in order, and every subtree query is a range query. That is how a tree problem becomes an array problem.
A second kind of Euler tour writes down the current node every time the DFS arrives at it, both on entry and when returning from a child. That sequence has length , and between the first occurrences of and the walk goes up from one to their LCA and down to the other without ever going higher. So the LCA is the shallowest node in that window — a range-minimum query over depths.
Mechanics
The running example (rooted at 0; values in brackets are used for path and subtree sums later):
flowchart TD
n0["0 (d0) [3]"] --> n1["1 (d1) [1]"]
n0 --> n2["2 (d1) [4]"]
n1 --> n3["3 (d2) [1]"]
n1 --> n4["4 (d2) [5]"]
n3 --> n5["5 (d3) [9]"]
n5 --> n6["6 (d4) [2]"]
n4 --> n11["11 (d3) [8]"]
n2 --> n7["7 (d2) [6]"]
n7 --> n8["8 (d3) [5]"]
n8 --> n9["9 (d4) [3]"]
n9 --> n10["10 (d5) [5]"]
Building the jump table
With nodes, the deepest possible jump we need is less than , so levels (0..3) suffice. The root's parent is set to the root itself, so jumps that would leave the tree stop at the root ("clamping"); this removes a special case from every query. Computed by script:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| depth | 0 | 1 | 1 | 2 | 2 | 3 | 4 | 2 | 3 | 4 | 5 | 3 |
| up[0] (parent) | 0 | 0 | 0 | 1 | 1 | 3 | 5 | 2 | 7 | 8 | 9 | 4 |
| up[1] (2 up) | 0 | 0 | 0 | 0 | 0 | 1 | 3 | 0 | 2 | 7 | 8 | 1 |
| up[2] (4 up) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 0 |
| up[3] (8 up) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Check one entry: , and indeed is four steps.
-th ancestor. For each set bit of , . If , report "none" first (clamping would silently return the root). Example: the 3rd ancestor of 10: , so jump 1 () then 2 (): answer 7.
LCA by binary lifting
flowchart TD
S["lca(u, v)"] --> D{"depth[u] < depth[v]?"}
D -->|"yes"| SW["swap u, v"]
D -->|"no"| LIFT
SW --> LIFT["lift u by depth[u] - depth[v]<br/>one jump per set bit"]
LIFT --> EQ{"u == v?"}
EQ -->|"yes"| R1["return u (v was an ancestor)"]
EQ -->|"no"| LOOP["for k = LOG-1 down to 0"]
LOOP --> T{"up[k][u] != up[k][v]?"}
T -->|"yes"| J["u = up[k][u], v = up[k][v]"]
T -->|"no"| NJ["skip: would reach a common ancestor"]
J --> NEXT["next k"]
NJ --> NEXT
NEXT --> R2["return up[0][u]"]
Trace: lca(10, 6) (computed by script; matches the visualizer below):
| step | k | u | v | up[k][u] | up[k][v] | action |
|---|---|---|---|---|---|---|
| start | – | 10 | 6 | – | – | depths 5 and 4; difference 1 = 0001₂ |
| lift | 0 | 10 → 9 | 6 | 9 | – | bit 0 set: u jumps 1 |
| check | – | 9 | 6 | – | – | same depth, |
| 1 | 3 | 9 | 6 | 0 | 0 | equal: skip (could overshoot) |
| 2 | 2 | 9 | 6 | 0 | 0 | equal: skip |
| 3 | 1 | 9 → 7 | 6 → 3 | 7 | 3 | differ: both jump 2 |
| 4 | 0 | 7 → 2 | 3 → 1 | 2 | 1 | differ: both jump 1 |
| end | – | 2 | 1 | – | – | return up[0][2] = 0 |
Other answers on this tree: , , (7 is an ancestor of 9, found right after lifting), .
Distance between and (number of edges): . ; ; .
-th node on the path from to : let . If , it is the -th ancestor of ; otherwise it is the -th ancestor of . The path is 10, 9, 8, 7, 2, 0, 1, 3, 5, 6.
Euler tour + RMQ: O(1) LCA
Record the node each time the DFS reaches it (children in increasing order). For the example tree (computed by script, entries):
| position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| node | 0 | 1 | 3 | 5 | 6 | 5 | 3 | 1 | 4 | 11 | 4 | 1 | 0 | 2 | 7 | 8 | 9 | 10 | 9 | 8 | 7 | 2 | 0 |
| depth | 0 | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 2 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 | 0 |
First occurrences: first = [0, 1, 13, 2, 8, 3, 4, 14, 15, 16, 17, 9] for nodes 0..11.
| query | first[u], first[v] | window | shallowest node in window | LCA |
|---|---|---|---|---|
| lca(10, 6) | 17, 4 | positions 4..17 | node 0 at position 12 (depth 0) | 0 |
| lca(5, 4) | 3, 8 | positions 3..8 | node 1 at position 7 (depth 1) | 1 |
| lca(9, 7) | 16, 14 | positions 14..16 | node 7 at position 14 (depth 2) | 7 |
Build a sparse table over the 23 positions that stores, for each power-of-two window, the node of minimum depth; min is idempotent, so every query is two table reads. Preprocessing for a sequence of length , query .
Tarjan's offline LCA (brief)
When all queries are known in advance, Tarjan's 1979 algorithm answers them in one DFS with a disjoint-set union (DSU):
- DFS from the root. On entering , make its own set and set
ancestor[find(v)] = v. - After finishing each child ,
union(v, c)and setancestor[find(v)] = v. - When is finished, mark it black. For every query with already black, the answer is
ancestor[find(w)].
Why it works: when finishes and is black, 's set has been merged up to the deepest ancestor of that is still on the DFS stack, and the deepest ancestor of on the stack while is being processed is exactly . Total time with path compression and union by rank, memory. It is elegant, but in practice binary lifting or the Euler tour is preferred unless memory is tight, because they work online.
Flattening: tin/tout and subtree queries
Number nodes in DFS entry order (), and let be the largest in 's subtree.
flowchart LR
T["tree: subtree of 1 = nodes 1, 3, 5, 6, 4, 11"] --> F["tin order: 0 1 3 5 6 4 11 2 7 8 9 10"]
F --> R["subtree of 1 = positions tin[1]..tout[1] = 1..6"]
R --> BIT["Fenwick tree over positions:<br/>subtree sum = range sum 1..6"]
F --> ANC["ancestor test:<br/>tin[u] <= tin[v] <= tout[u]"]
Computed by script on the example (children visited in increasing order):
| node | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| tin | 0 | 1 | 7 | 2 | 5 | 3 | 4 | 8 | 9 | 10 | 11 | 6 |
| tout | 11 | 6 | 11 | 4 | 6 | 4 | 4 | 11 | 11 | 11 | 11 | 6 |
| value | 3 | 1 | 4 | 1 | 5 | 9 | 2 | 6 | 5 | 3 | 5 | 8 |
| subtree sum | 52 | 26 | 23 | 12 | 13 | 11 | 2 | 19 | 13 | 8 | 5 | 8 |
The flattened value array (value at position ) is [3, 1, 1, 9, 2, 5, 8, 4, 6, 5, 3, 5]. The subtree of 1 is positions 1..6: . Adding 10 to node 3 is a point update at position ; afterwards subtree(1) = 36 and subtree(0) = 62, while subtree(2) stays 23. With a Fenwick tree each update and query is — this is CSES "Subtree Queries".
Root-to-node sums with updates use the dual trick: a point update to 's value changes the root-path sum of every node in 's subtree, so it is a range add on , and reading the root-path sum of is a point query at . A Fenwick tree over a difference array does both in — CSES "Path Queries".
Path queries with prefix sums and LCA
Let be the sum of values from the root to inclusive. The path consists of the root path of plus the root path of , minus the root path of twice, plus itself once (it was subtracted twice but belongs to the path):
Root sums on the example: [3, 4, 7, 5, 9, 14, 16, 13, 18, 21, 26, 17]. (check: ). For edge weights instead of node values, store each edge's weight at its child and drop the term. XOR works the same way (and the term cancels to nothing because ).
Path updates read at the end (add to every node on , many times, then report every node): the difference on a tree. Do diff[u] += x, diff[v] += x, diff[w] -= x, diff[parent(w)] -= x; at the end each node's total is the sum of diff over its subtree. A node on the path gets exactly once; nodes above get . This is CSES "Counting Paths".
Path maximum (static): store , the maximum on the edges above , alongside : . The LCA routine takes the max of every jump it makes. Max is not invertible, so prefix sums cannot do this, but jumps can.
Binary lifting on a functional graph
In a functional graph every node has exactly one successor (teleporters, permutation cycles, "next state" functions). There is no root and there may be cycles, but the doubling table still works: and . The -th successor is one jump per set bit of , so up to costs 30 jumps after building 30 levels.
Example: (node teleports to ). From 0 the walk is (a 3-cycle), so the 5th successor of 0 is 4; from 7: and then the 3-cycle, so the 10th successor of 7 is 0; from 3: (a 2-cycle), so the 13th successor of 3 is 1. This is CSES "Planets Queries I". The same table supports "first time the walk reaches a node satisfying a monotone property" by the same top-down binary search as the LCA loop.
The ladder: brute force → better → optimal
Rung 0: mark-and-climb, per query. Walk from to the root marking nodes, then walk from until hitting a mark. Needs a visited set per query. On a path-shaped tree with , up to steps.
Rung 1: equalise depths and climb together, per query, memory. No marks, still linear in the depth. Good enough when the tree is guaranteed balanced (heights of 20–40) or queries are few.
Rung 2: binary lifting, build, query. One table, answers LCA, -th ancestor, -th node on a path, and static path aggregates (max, min, gcd — anything associative). The default in contests.
Rung 3: Euler tour + sparse table, build, query. Faster per query, but the table is twice as long ( positions) and it only answers LCA. Worth it when or queries sit in an inner loop (for example, sorting nodes into a virtual tree, which makes LCA calls).
Rung 4: offline Tarjan, . Linear in practice, memory, but the queries must all be known first.
Rung 5 (theory): build, query. Bender–Farach-Colton's -RMQ over the Euler depth sequence (adjacent depths differ by exactly 1, so blocks of size have only distinct shapes, which can all be tabulated), or Schieber–Vishkin. Rarely implemented outside libraries.
| Rung | Build | Query | Memory | Online | Extras |
|---|---|---|---|---|---|
| 0 mark-and-climb | yes | – | |||
| 1 climb together | yes | – | |||
| 2 binary lifting | yes | -th ancestor, path aggregates | |||
| 3 Euler tour + sparse table | yes | ancestor test via tin/tout | |||
| 4 Tarjan offline | amortised | no | – | ||
| 5 Bender–Farach-Colton | yes | complex |
Correctness
The jump table
Claim. is the -th ancestor of , or the root if has depth less than .
Proof by induction on . For it is the parent (root clamped to itself). For , going up levels is going up levels and then more, so ; clamping composes because the root's ancestor at any distance is the root. The construction fills level only after level is complete for all nodes, so every lookup reads a finished value.
LCA by binary lifting
Let with .
Phase 1 (lift). Jumping by each set bit of moves it up exactly levels (by the table claim, as the jumps never exceed the depth). The ancestor of at depth has the same common ancestors with as does, because every common ancestor of and has depth at most . So the LCA is unchanged. If now , then was an ancestor of the original , and it is the LCA.
Phase 2 (jump together). Now at the same depth, and is a proper ancestor of both. Let : the number of levels we may climb while staying strictly below . Invariant: before processing bit , the remaining climb (levels still to go before reaching the children of ) satisfies , and . Jumping keeps the two nodes distinct iff , because ancestors at the same height above and coincide exactly when that height reaches . So the loop jumps exactly when bit of is set, and the invariant holds for . Initially , so the invariant holds for . After , : and are distinct children of , and .
Euler tour RMQ
Claim. In the Euler sequence, the window between and contains and no node shallower than .
Proof. Assume . If , then is in 's subtree; the DFS does not leave 's subtree between entering and first reaching , so every node in the window is a descendant of (depth ), and is at the left end. Otherwise and lie in different child subtrees of . The DFS enters 's subtree, finishes it, returns to (writing into the sequence), and later enters the child subtree containing . Throughout, it stays inside 's subtree, because it cannot leave while has unvisited children (the one containing ). So appears in the window, every node in the window is a descendant of , and the shallowest one is — the only node of depth in 's subtree.
Subtree ranges
Claim. is in the subtree of iff .
Proof. The DFS assigns entry times consecutively. Between entering (time ) and leaving it, it enters exactly the nodes of 's subtree and no others (it cannot visit a non-descendant without returning above first). So the subtree's entry times are a contiguous block starting at , whose last element is by definition .
Complexity
| Operation | Binary lifting | Euler tour + sparse table | Tarjan offline |
|---|---|---|---|
| preprocessing | on entries | ||
| LCA query | amortised | ||
| -th ancestor | not supported | not supported | |
| memory | ints | ints |
For : binary lifting stores integers (14 MB as 32-bit); the Euler sparse table has positions and 19 levels, integers (30 MB).
Constants and cache. A binary-lifting query performs up to dependent random memory reads — each jump's address depends on the previous jump's result, so the CPU cannot overlap them. Storing the table as up[k][v] (level-major) makes the build stream through memory; storing it as up[v][k] (node-major) makes a single node's jumps share cache lines but the build stride-heavy. Measured differences are small for and favour level-major for the build at . The Euler-tour query performs two independent reads, which is why it wins at very high query counts. Tarjan's algorithm is recursive; on deep trees, convert the DFS to an explicit stack (all implementations on this page are iterative for that reason — Python's default recursion limit is 1,000 and even C++ can overflow the default 1 MB Windows stack on a -node path).
Flattening costs one DFS (); afterwards each subtree query or update costs whatever the array structure costs ( with a Fenwick tree).
Implementation
Two code groups, each with the same tests in all four languages, on the 12-node example tree.
TreeLCA: BFS for parent and depth, the binary-lifting table,kthAncestor,lca,dist, and an independent Euler tour + sparse tablelcaRmq; the tests check both LCA methods against each other.- Flattening: iterative DFS for
tin/tout, a Fenwick tree for subtree sums with point updates, and a second Fenwick tree (range add, point query) for root-path sums, giving dynamic path sums.
from collections import deque
class TreeLCA:
def __init__(self, n: int, edges: list[tuple[int, int]], root: int = 0):
adj: list[list[int]] = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
for nb in adj:
nb.sort()
parent, self.depth = [root] * n, [0] * n # root's parent is itself (clamping)
seen = [False] * n
seen[root] = True
q = deque([root])
while q:
x = q.popleft()
for y in adj[x]:
if not seen[y]:
seen[y] = True
parent[y], self.depth[y] = x, self.depth[x] + 1
q.append(y)
self.log = max(1, (n - 1).bit_length())
self.up = [parent]
for _ in range(1, self.log):
prev = self.up[-1]
self.up.append([prev[prev[v]] for v in range(n)])
# Euler tour (2n - 1 entries) with an iterative DFS, children in increasing order
self.euler, self.first, it = [root], [0] * n, [0] * n
stack = [root]
while stack:
x = stack[-1]
if it[x] < len(adj[x]):
y = adj[x][it[x]]
it[x] += 1
if self.depth[y] == self.depth[x] + 1: # y is a child of x
self.first[y] = len(self.euler)
self.euler.append(y)
stack.append(y)
else:
stack.pop()
if stack:
self.euler.append(stack[-1])
# sparse table over Euler positions: node of minimum depth
self.st = [self.euler[:]]
k = 1
while (1 << k) <= len(self.euler):
p, h = self.st[-1], 1 << (k - 1)
self.st.append([p[i] if self.depth[p[i]] <= self.depth[p[i + h]] else p[i + h]
for i in range(len(self.euler) - (1 << k) + 1)])
k += 1
def kth_ancestor(self, v: int, k: int) -> int:
if k > self.depth[v]:
return -1
for b in range(self.log):
if k >> b & 1:
v = self.up[b][v]
return v
def lca(self, u: int, v: int) -> int:
if self.depth[u] < self.depth[v]:
u, v = v, u
u = self.kth_ancestor(u, self.depth[u] - self.depth[v])
if u == v:
return u
for k in range(self.log - 1, -1, -1):
if self.up[k][u] != self.up[k][v]:
u, v = self.up[k][u], self.up[k][v]
return self.up[0][u]
def dist(self, u: int, v: int) -> int:
return self.depth[u] + self.depth[v] - 2 * self.depth[self.lca(u, v)]
def lca_rmq(self, u: int, v: int) -> int:
l, r = sorted((self.first[u], self.first[v]))
k = (r - l + 1).bit_length() - 1
a, b = self.st[k][l], self.st[k][r - (1 << k) + 1]
return a if self.depth[a] <= self.depth[b] else b
if __name__ == "__main__":
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (3, 5), (5, 6), (2, 7), (7, 8), (8, 9), (9, 10), (4, 11)]
t = TreeLCA(12, edges)
pairs = [(10, 6), (6, 11), (5, 4), (9, 7), (10, 10), (11, 0), (8, 3)]
expected = [0, 1, 1, 7, 10, 0, 0]
assert [t.lca(a, b) for a, b in pairs] == expected
assert [t.lca_rmq(a, b) for a, b in pairs] == expected
assert all(t.lca(a, b) == t.lca_rmq(a, b) for a in range(12) for b in range(12))
assert [t.dist(10, 6), t.dist(6, 11), t.dist(9, 7)] == [9, 5, 2]
assert [t.kth_ancestor(10, 3), t.kth_ancestor(10, 5), t.kth_ancestor(10, 6), t.kth_ancestor(6, 2)] == [7, 0, -1, 3]
assert len(t.euler) == 23 and t.first == [0, 1, 13, 2, 8, 3, 4, 14, 15, 16, 17, 9]
print("all tests pass")
import java.util.*;
public class TreeLCA {
final int n, log;
final int[] depth, first;
final int[][] up, st;
final int[] euler;
TreeLCA(int n, int[][] edges, int root) {
this.n = n;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
for (List<Integer> nb : adj) Collections.sort(nb);
int[] parent = new int[n];
depth = new int[n];
boolean[] seen = new boolean[n];
ArrayDeque<Integer> q = new ArrayDeque<>();
parent[root] = root; seen[root] = true; q.add(root);
while (!q.isEmpty()) {
int x = q.poll();
for (int y : adj.get(x)) if (!seen[y]) { seen[y] = true; parent[y] = x; depth[y] = depth[x] + 1; q.add(y); }
}
log = Math.max(1, 32 - Integer.numberOfLeadingZeros(n - 1));
up = new int[log][];
up[0] = parent;
for (int k = 1; k < log; k++) {
up[k] = new int[n];
for (int v = 0; v < n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
}
// Euler tour, iterative DFS, children in increasing order
euler = new int[2 * n - 1];
first = new int[n];
int[] it = new int[n];
int len = 0;
int[] stack = new int[n];
int top = 0;
stack[top++] = root; euler[len++] = root;
while (top > 0) {
int x = stack[top - 1];
if (it[x] < adj.get(x).size()) {
int y = adj.get(x).get(it[x]++);
if (depth[y] == depth[x] + 1) { first[y] = len; euler[len++] = y; stack[top++] = y; }
} else {
top--;
if (top > 0) euler[len++] = stack[top - 1];
}
}
int m = euler.length, levels = 32 - Integer.numberOfLeadingZeros(m);
st = new int[levels][];
st[0] = euler.clone();
for (int k = 1; k < levels; k++) {
int h = 1 << (k - 1), cnt = m - (1 << k) + 1;
st[k] = new int[cnt];
for (int i = 0; i < cnt; i++) {
int a = st[k - 1][i], b = st[k - 1][i + h];
st[k][i] = depth[a] <= depth[b] ? a : b;
}
}
}
int kthAncestor(int v, int k) {
if (k > depth[v]) return -1;
for (int b = 0; b < log; b++) if ((k >> b & 1) == 1) v = up[b][v];
return v;
}
int lca(int u, int v) {
if (depth[u] < depth[v]) { int t = u; u = v; v = t; }
u = kthAncestor(u, depth[u] - depth[v]);
if (u == v) return u;
for (int k = log - 1; k >= 0; k--)
if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
return up[0][u];
}
int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }
int lcaRmq(int u, int v) {
int l = Math.min(first[u], first[v]), r = Math.max(first[u], first[v]);
int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);
int a = st[k][l], b = st[k][r - (1 << k) + 1];
return depth[a] <= depth[b] ? a : b;
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {3, 5}, {5, 6}, {2, 7}, {7, 8}, {8, 9}, {9, 10}, {4, 11}};
TreeLCA t = new TreeLCA(12, edges, 0);
int[][] pairs = {{10, 6}, {6, 11}, {5, 4}, {9, 7}, {10, 10}, {11, 0}, {8, 3}};
int[] expected = {0, 1, 1, 7, 10, 0, 0};
for (int i = 0; i < pairs.length; i++) {
check(t.lca(pairs[i][0], pairs[i][1]) == expected[i], "lca " + i);
check(t.lcaRmq(pairs[i][0], pairs[i][1]) == expected[i], "rmq " + i);
}
for (int a = 0; a < 12; a++) for (int b = 0; b < 12; b++) check(t.lca(a, b) == t.lcaRmq(a, b), "all pairs");
check(t.dist(10, 6) == 9 && t.dist(6, 11) == 5 && t.dist(9, 7) == 2, "dist");
check(t.kthAncestor(10, 3) == 7 && t.kthAncestor(10, 5) == 0 && t.kthAncestor(10, 6) == -1 && t.kthAncestor(6, 2) == 3, "kth");
check(Arrays.equals(t.first, new int[]{0, 1, 13, 2, 8, 3, 4, 14, 15, 16, 17, 9}), "first");
System.out.println("all tests pass");
}
}
#include <algorithm>
#include <bit>
#include <cassert>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
struct TreeLCA {
int n, log;
std::vector<int> depth, first, euler;
std::vector<std::vector<int>> up, st;
TreeLCA(int n_, const std::vector<std::pair<int, int>>& edges, int root = 0) : n(n_), depth(n_, 0), first(n_, 0) {
std::vector<std::vector<int>> adj(n);
for (auto [a, b] : edges) { adj[a].push_back(b); adj[b].push_back(a); }
for (auto& nb : adj) std::sort(nb.begin(), nb.end());
std::vector<int> parent(n, root);
std::vector<bool> seen(n, false);
std::queue<int> q;
seen[root] = true; q.push(root);
while (!q.empty()) {
int x = q.front(); q.pop();
for (int y : adj[x]) if (!seen[y]) { seen[y] = true; parent[y] = x; depth[y] = depth[x] + 1; q.push(y); }
}
log = std::max(1, static_cast<int>(std::bit_width(static_cast<unsigned>(n - 1))));
up.assign(log, std::vector<int>(n));
up[0] = parent;
for (int k = 1; k < log; ++k)
for (int v = 0; v < n; ++v) up[k][v] = up[k - 1][up[k - 1][v]];
// Euler tour, iterative DFS, children in increasing order
std::vector<int> it(n, 0), stack{root};
euler.push_back(root);
while (!stack.empty()) {
int x = stack.back();
if (it[x] < static_cast<int>(adj[x].size())) {
int y = adj[x][it[x]++];
if (depth[y] == depth[x] + 1) { first[y] = static_cast<int>(euler.size()); euler.push_back(y); stack.push_back(y); }
} else {
stack.pop_back();
if (!stack.empty()) euler.push_back(stack.back());
}
}
int m = static_cast<int>(euler.size());
int levels = std::bit_width(static_cast<unsigned>(m));
st.assign(levels, {});
st[0] = euler;
for (int k = 1; k < levels; ++k) {
int h = 1 << (k - 1), cnt = m - (1 << k) + 1;
st[k].resize(cnt);
for (int i = 0; i < cnt; ++i) {
int a = st[k - 1][i], b = st[k - 1][i + h];
st[k][i] = depth[a] <= depth[b] ? a : b;
}
}
}
int kthAncestor(int v, int k) const {
if (k > depth[v]) return -1;
for (int b = 0; b < log; ++b) if (k >> b & 1) v = up[b][v];
return v;
}
int lca(int u, int v) const {
if (depth[u] < depth[v]) std::swap(u, v);
u = kthAncestor(u, depth[u] - depth[v]);
if (u == v) return u;
for (int k = log - 1; k >= 0; --k)
if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
return up[0][u];
}
int dist(int u, int v) const { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }
int lcaRmq(int u, int v) const {
int l = std::min(first[u], first[v]), r = std::max(first[u], first[v]);
int k = std::bit_width(static_cast<unsigned>(r - l + 1)) - 1;
int a = st[k][l], b = st[k][r - (1 << k) + 1];
return depth[a] <= depth[b] ? a : b;
}
};
int main() {
std::vector<std::pair<int, int>> edges{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {3, 5}, {5, 6}, {2, 7}, {7, 8}, {8, 9}, {9, 10}, {4, 11}};
TreeLCA t(12, edges);
std::vector<std::pair<int, int>> pairs{{10, 6}, {6, 11}, {5, 4}, {9, 7}, {10, 10}, {11, 0}, {8, 3}};
std::vector<int> expected{0, 1, 1, 7, 10, 0, 0};
for (std::size_t i = 0; i < pairs.size(); ++i) {
assert(t.lca(pairs[i].first, pairs[i].second) == expected[i]);
assert(t.lcaRmq(pairs[i].first, pairs[i].second) == expected[i]);
}
for (int a = 0; a < 12; ++a) for (int b = 0; b < 12; ++b) assert(t.lca(a, b) == t.lcaRmq(a, b));
assert(t.dist(10, 6) == 9 && t.dist(6, 11) == 5 && t.dist(9, 7) == 2);
assert(t.kthAncestor(10, 3) == 7 && t.kthAncestor(10, 5) == 0 && t.kthAncestor(10, 6) == -1 && t.kthAncestor(6, 2) == 3);
assert((t.first == std::vector<int>{0, 1, 13, 2, 8, 3, 4, 14, 15, 16, 17, 9}));
std::cout << "all tests pass\n";
}
class TreeLCA {
depth: number[];
first: number[];
euler: number[];
up: number[][];
st: number[][];
log: number;
constructor(n: number, edges: [number, number][], root = 0) {
const adj: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
for (const nb of adj) nb.sort((x, y) => x - y);
const parent = new Array<number>(n).fill(root);
this.depth = new Array<number>(n).fill(0);
const seen = new Array<boolean>(n).fill(false);
seen[root] = true;
const q = [root];
for (let h = 0; h < q.length; h++) {
const x = q[h];
for (const y of adj[x]) if (!seen[y]) { seen[y] = true; parent[y] = x; this.depth[y] = this.depth[x] + 1; q.push(y); }
}
this.log = Math.max(1, 32 - Math.clz32(n - 1));
this.up = [parent];
for (let k = 1; k < this.log; k++) {
const prev = this.up[k - 1];
this.up.push(prev.map((p) => prev[p]));
}
// Euler tour, iterative DFS, children in increasing order
this.euler = [root];
this.first = new Array<number>(n).fill(0);
const it = new Array<number>(n).fill(0);
const stack = [root];
while (stack.length > 0) {
const x = stack[stack.length - 1];
if (it[x] < adj[x].length) {
const y = adj[x][it[x]++];
if (this.depth[y] === this.depth[x] + 1) { this.first[y] = this.euler.length; this.euler.push(y); stack.push(y); }
} else {
stack.pop();
if (stack.length > 0) this.euler.push(stack[stack.length - 1]);
}
}
const m = this.euler.length;
this.st = [this.euler.slice()];
for (let k = 1; (1 << k) <= m; k++) {
const p = this.st[k - 1], h = 1 << (k - 1), row: number[] = [];
for (let i = 0; i + (1 << k) <= m; i++) row.push(this.depth[p[i]] <= this.depth[p[i + h]] ? p[i] : p[i + h]);
this.st.push(row);
}
}
kthAncestor(v: number, k: number): number {
if (k > this.depth[v]) return -1;
for (let b = 0; b < this.log; b++) if ((k >> b) & 1) v = this.up[b][v];
return v;
}
lca(u: number, v: number): number {
if (this.depth[u] < this.depth[v]) [u, v] = [v, u];
u = this.kthAncestor(u, this.depth[u] - this.depth[v]);
if (u === v) return u;
for (let k = this.log - 1; k >= 0; k--) {
if (this.up[k][u] !== this.up[k][v]) { u = this.up[k][u]; v = this.up[k][v]; }
}
return this.up[0][u];
}
dist(u: number, v: number): number {
return this.depth[u] + this.depth[v] - 2 * this.depth[this.lca(u, v)];
}
lcaRmq(u: number, v: number): number {
const l = Math.min(this.first[u], this.first[v]), r = Math.max(this.first[u], this.first[v]);
const k = 31 - Math.clz32(r - l + 1);
const a = this.st[k][l], b = this.st[k][r - (1 << k) + 1];
return this.depth[a] <= this.depth[b] ? a : b;
}
}
function assert(ok: boolean, msg: string): void { if (!ok) throw new Error(msg); }
const edges: [number, number][] = [[0, 1], [0, 2], [1, 3], [1, 4], [3, 5], [5, 6], [2, 7], [7, 8], [8, 9], [9, 10], [4, 11]];
const t = new TreeLCA(12, edges);
const pairs: [number, number][] = [[10, 6], [6, 11], [5, 4], [9, 7], [10, 10], [11, 0], [8, 3]];
const expected = [0, 1, 1, 7, 10, 0, 0];
pairs.forEach(([a, b], i) => {
assert(t.lca(a, b) === expected[i], `lca ${i}`);
assert(t.lcaRmq(a, b) === expected[i], `rmq ${i}`);
});
for (let a = 0; a < 12; a++) for (let b = 0; b < 12; b++) assert(t.lca(a, b) === t.lcaRmq(a, b), "all pairs");
assert(t.dist(10, 6) === 9 && t.dist(6, 11) === 5 && t.dist(9, 7) === 2, "dist");
assert(t.kthAncestor(10, 3) === 7 && t.kthAncestor(10, 5) === 0 && t.kthAncestor(10, 6) === -1 && t.kthAncestor(6, 2) === 3, "kth");
assert(t.euler.length === 23 && t.first.join(",") === "0,1,13,2,8,3,4,14,15,16,17,9", "first");
console.log("all tests pass");
The second group flattens the tree. subtree(v) is a range sum over in a Fenwick tree indexed by ; rootSum(v) is a point query in a second Fenwick tree that receives a range add over whenever 's value changes. The LCA inside pathSum is found by climbing with the ancestor test — deliberately simple so that this block stands alone; in a real solution use TreeLCA.lca.
class Fenwick:
def __init__(self, n: int):
self.t = [0] * (n + 1)
def add(self, i: int, d: int) -> None: # 0-indexed position
i += 1
while i < len(self.t):
self.t[i] += d
i += i & -i
def prefix(self, i: int) -> int: # sum of positions 0..i
i += 1
s = 0
while i > 0:
s += self.t[i]
i -= i & -i
return s
def range_sum(self, l: int, r: int) -> int:
return self.prefix(r) - (self.prefix(l - 1) if l > 0 else 0)
class FlatTree:
def __init__(self, n: int, edges: list[tuple[int, int]], values: list[int], root: int = 0):
adj: list[list[int]] = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
for nb in adj:
nb.sort()
self.parent, self.tin, self.tout = [-1] * n, [0] * n, [0] * n
timer, it, stack = 0, [0] * n, [root]
self.tin[root] = timer
timer += 1
while stack: # iterative DFS: entry and exit times
x = stack[-1]
if it[x] < len(adj[x]):
y = adj[x][it[x]]
it[x] += 1
if y != self.parent[x]:
self.parent[y] = x
self.tin[y] = timer
timer += 1
stack.append(y)
else:
self.tout[x] = timer - 1
stack.pop()
self.val = values[:]
self.sub = Fenwick(n) # point value at tin[v]
self.path = Fenwick(n + 1) # difference array: range add, point query
for v in range(n):
self._apply(v, values[v])
def _apply(self, v: int, d: int) -> None:
self.sub.add(self.tin[v], d)
self.path.add(self.tin[v], d)
self.path.add(self.tout[v] + 1, -d)
def add(self, v: int, d: int) -> None:
self.val[v] += d
self._apply(v, d)
def is_ancestor(self, u: int, v: int) -> bool:
return self.tin[u] <= self.tin[v] <= self.tout[u]
def subtree(self, v: int) -> int:
return self.sub.range_sum(self.tin[v], self.tout[v])
def root_sum(self, v: int) -> int:
return self.path.prefix(self.tin[v])
def path_sum(self, u: int, v: int) -> int:
w = u
while not self.is_ancestor(w, v): # climb to the LCA (simple; use binary lifting in practice)
w = self.parent[w]
return self.root_sum(u) + self.root_sum(v) - 2 * self.root_sum(w) + self.val[w]
if __name__ == "__main__":
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (3, 5), (5, 6), (2, 7), (7, 8), (8, 9), (9, 10), (4, 11)]
values = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8]
f = FlatTree(12, edges, values)
assert f.tin == [0, 1, 7, 2, 5, 3, 4, 8, 9, 10, 11, 6]
assert f.tout == [11, 6, 11, 4, 6, 4, 4, 11, 11, 11, 11, 6]
assert [f.subtree(v) for v in range(12)] == [52, 26, 23, 12, 13, 11, 2, 19, 13, 8, 5, 8]
assert [f.root_sum(v) for v in range(12)] == [3, 4, 7, 5, 9, 14, 16, 13, 18, 21, 26, 17]
assert [f.path_sum(10, 6), f.path_sum(6, 11), f.path_sum(9, 7)] == [39, 26, 14]
assert f.is_ancestor(1, 6) and not f.is_ancestor(2, 6)
f.add(3, 10)
assert [f.subtree(1), f.subtree(0), f.subtree(2)] == [36, 62, 23]
assert [f.path_sum(10, 6), f.path_sum(6, 11), f.path_sum(9, 7)] == [49, 36, 14]
print("all tests pass")
import java.util.*;
public class FlatTree {
static final class Fenwick {
final long[] t;
Fenwick(int n) { t = new long[n + 1]; }
void add(int i, long d) { for (i++; i < t.length; i += i & -i) t[i] += d; }
long prefix(int i) { long s = 0; for (i++; i > 0; i -= i & -i) s += t[i]; return s; }
long rangeSum(int l, int r) { return prefix(r) - (l > 0 ? prefix(l - 1) : 0); }
}
final int[] parent, tin, tout;
final long[] val;
final Fenwick sub, path;
FlatTree(int n, int[][] edges, int[] values, int root) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
for (List<Integer> nb : adj) Collections.sort(nb);
parent = new int[n]; tin = new int[n]; tout = new int[n];
Arrays.fill(parent, -1);
int timer = 0;
int[] it = new int[n], stack = new int[n];
int top = 0;
stack[top++] = root; tin[root] = timer++;
while (top > 0) {
int x = stack[top - 1];
if (it[x] < adj.get(x).size()) {
int y = adj.get(x).get(it[x]++);
if (y != parent[x]) { parent[y] = x; tin[y] = timer++; stack[top++] = y; }
} else {
tout[x] = timer - 1;
top--;
}
}
val = new long[n];
sub = new Fenwick(n);
path = new Fenwick(n + 1);
for (int v = 0; v < n; v++) { val[v] = values[v]; apply(v, values[v]); }
}
private void apply(int v, long d) {
sub.add(tin[v], d);
path.add(tin[v], d);
path.add(tout[v] + 1, -d);
}
void add(int v, long d) { val[v] += d; apply(v, d); }
boolean isAncestor(int u, int v) { return tin[u] <= tin[v] && tin[v] <= tout[u]; }
long subtree(int v) { return sub.rangeSum(tin[v], tout[v]); }
long rootSum(int v) { return path.prefix(tin[v]); }
long pathSum(int u, int v) {
int w = u;
while (!isAncestor(w, v)) w = parent[w];
return rootSum(u) + rootSum(v) - 2 * rootSum(w) + val[w];
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {3, 5}, {5, 6}, {2, 7}, {7, 8}, {8, 9}, {9, 10}, {4, 11}};
int[] values = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8};
FlatTree f = new FlatTree(12, edges, values, 0);
check(Arrays.equals(f.tin, new int[]{0, 1, 7, 2, 5, 3, 4, 8, 9, 10, 11, 6}), "tin");
check(Arrays.equals(f.tout, new int[]{11, 6, 11, 4, 6, 4, 4, 11, 11, 11, 11, 6}), "tout");
long[] subs = {52, 26, 23, 12, 13, 11, 2, 19, 13, 8, 5, 8};
long[] roots = {3, 4, 7, 5, 9, 14, 16, 13, 18, 21, 26, 17};
for (int v = 0; v < 12; v++) { check(f.subtree(v) == subs[v], "sub " + v); check(f.rootSum(v) == roots[v], "root " + v); }
check(f.pathSum(10, 6) == 39 && f.pathSum(6, 11) == 26 && f.pathSum(9, 7) == 14, "path");
check(f.isAncestor(1, 6) && !f.isAncestor(2, 6), "ancestor");
f.add(3, 10);
check(f.subtree(1) == 36 && f.subtree(0) == 62 && f.subtree(2) == 23, "sub after");
check(f.pathSum(10, 6) == 49 && f.pathSum(6, 11) == 36 && f.pathSum(9, 7) == 14, "path after");
System.out.println("all tests pass");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
struct Fenwick {
std::vector<long long> t;
explicit Fenwick(int n) : t(n + 1, 0) {}
void add(int i, long long d) { for (++i; i < static_cast<int>(t.size()); i += i & -i) t[i] += d; }
long long prefix(int i) const { long long s = 0; for (++i; i > 0; i -= i & -i) s += t[i]; return s; }
long long rangeSum(int l, int r) const { return prefix(r) - (l > 0 ? prefix(l - 1) : 0); }
};
struct FlatTree {
std::vector<int> parent, tin, tout;
std::vector<long long> val;
Fenwick sub, path;
FlatTree(int n, const std::vector<std::pair<int, int>>& edges, const std::vector<int>& values, int root = 0)
: parent(n, -1), tin(n, 0), tout(n, 0), val(values.begin(), values.end()), sub(n), path(n + 1) {
std::vector<std::vector<int>> adj(n);
for (auto [a, b] : edges) { adj[a].push_back(b); adj[b].push_back(a); }
for (auto& nb : adj) std::sort(nb.begin(), nb.end());
int timer = 0;
std::vector<int> it(n, 0), stack{root};
tin[root] = timer++;
while (!stack.empty()) {
int x = stack.back();
if (it[x] < static_cast<int>(adj[x].size())) {
int y = adj[x][it[x]++];
if (y != parent[x]) { parent[y] = x; tin[y] = timer++; stack.push_back(y); }
} else {
tout[x] = timer - 1;
stack.pop_back();
}
}
for (int v = 0; v < n; ++v) apply(v, values[v]);
}
void apply(int v, long long d) {
sub.add(tin[v], d);
path.add(tin[v], d);
path.add(tout[v] + 1, -d);
}
void add(int v, long long d) { val[v] += d; apply(v, d); }
bool isAncestor(int u, int v) const { return tin[u] <= tin[v] && tin[v] <= tout[u]; }
long long subtree(int v) const { return sub.rangeSum(tin[v], tout[v]); }
long long rootSum(int v) const { return path.prefix(tin[v]); }
long long pathSum(int u, int v) const {
int w = u;
while (!isAncestor(w, v)) w = parent[w];
return rootSum(u) + rootSum(v) - 2 * rootSum(w) + val[w];
}
};
int main() {
std::vector<std::pair<int, int>> edges{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {3, 5}, {5, 6}, {2, 7}, {7, 8}, {8, 9}, {9, 10}, {4, 11}};
std::vector<int> values{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8};
FlatTree f(12, edges, values);
assert((f.tin == std::vector<int>{0, 1, 7, 2, 5, 3, 4, 8, 9, 10, 11, 6}));
assert((f.tout == std::vector<int>{11, 6, 11, 4, 6, 4, 4, 11, 11, 11, 11, 6}));
std::vector<long long> subs{52, 26, 23, 12, 13, 11, 2, 19, 13, 8, 5, 8};
std::vector<long long> roots{3, 4, 7, 5, 9, 14, 16, 13, 18, 21, 26, 17};
for (int v = 0; v < 12; ++v) { assert(f.subtree(v) == subs[v]); assert(f.rootSum(v) == roots[v]); }
assert(f.pathSum(10, 6) == 39 && f.pathSum(6, 11) == 26 && f.pathSum(9, 7) == 14);
assert(f.isAncestor(1, 6) && !f.isAncestor(2, 6));
f.add(3, 10);
assert(f.subtree(1) == 36 && f.subtree(0) == 62 && f.subtree(2) == 23);
assert(f.pathSum(10, 6) == 49 && f.pathSum(6, 11) == 36 && f.pathSum(9, 7) == 14);
std::cout << "all tests pass\n";
}
class Fenwick {
t: number[];
constructor(n: number) { this.t = new Array<number>(n + 1).fill(0); }
add(i: number, d: number): void { for (i++; i < this.t.length; i += i & -i) this.t[i] += d; }
prefix(i: number): number { let s = 0; for (i++; i > 0; i -= i & -i) s += this.t[i]; return s; }
rangeSum(l: number, r: number): number { return this.prefix(r) - (l > 0 ? this.prefix(l - 1) : 0); }
}
class FlatTree {
parent: number[];
tin: number[];
tout: number[];
val: number[];
sub: Fenwick;
path: Fenwick;
constructor(n: number, edges: [number, number][], values: number[], root = 0) {
const adj: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
for (const nb of adj) nb.sort((x, y) => x - y);
this.parent = new Array<number>(n).fill(-1);
this.tin = new Array<number>(n).fill(0);
this.tout = new Array<number>(n).fill(0);
let timer = 0;
const it = new Array<number>(n).fill(0), stack = [root];
this.tin[root] = timer++;
while (stack.length > 0) {
const x = stack[stack.length - 1];
if (it[x] < adj[x].length) {
const y = adj[x][it[x]++];
if (y !== this.parent[x]) { this.parent[y] = x; this.tin[y] = timer++; stack.push(y); }
} else {
this.tout[x] = timer - 1;
stack.pop();
}
}
this.val = values.slice();
this.sub = new Fenwick(n);
this.path = new Fenwick(n + 1);
values.forEach((v, i) => this.apply(i, v));
}
apply(v: number, d: number): void {
this.sub.add(this.tin[v], d);
this.path.add(this.tin[v], d);
this.path.add(this.tout[v] + 1, -d);
}
add(v: number, d: number): void { this.val[v] += d; this.apply(v, d); }
isAncestor(u: number, v: number): boolean { return this.tin[u] <= this.tin[v] && this.tin[v] <= this.tout[u]; }
subtree(v: number): number { return this.sub.rangeSum(this.tin[v], this.tout[v]); }
rootSum(v: number): number { return this.path.prefix(this.tin[v]); }
pathSum(u: number, v: number): number {
let w = u;
while (!this.isAncestor(w, v)) w = this.parent[w];
return this.rootSum(u) + this.rootSum(v) - 2 * this.rootSum(w) + this.val[w];
}
}
function assert(ok: boolean, msg: string): void { if (!ok) throw new Error(msg); }
const edges: [number, number][] = [[0, 1], [0, 2], [1, 3], [1, 4], [3, 5], [5, 6], [2, 7], [7, 8], [8, 9], [9, 10], [4, 11]];
const f = new FlatTree(12, edges, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8]);
assert(f.tin.join(",") === "0,1,7,2,5,3,4,8,9,10,11,6", "tin");
assert(f.tout.join(",") === "11,6,11,4,6,4,4,11,11,11,11,6", "tout");
const subs = [52, 26, 23, 12, 13, 11, 2, 19, 13, 8, 5, 8];
const roots = [3, 4, 7, 5, 9, 14, 16, 13, 18, 21, 26, 17];
for (let v = 0; v < 12; v++) { assert(f.subtree(v) === subs[v], `sub ${v}`); assert(f.rootSum(v) === roots[v], `root ${v}`); }
assert(f.pathSum(10, 6) === 39 && f.pathSum(6, 11) === 26 && f.pathSum(9, 7) === 14, "path");
assert(f.isAncestor(1, 6) && !f.isAncestor(2, 6), "ancestor");
f.add(3, 10);
assert(f.subtree(1) === 36 && f.subtree(0) === 62 && f.subtree(2) === 23, "sub after");
assert(f.pathSum(10, 6) === 49 && f.pathSum(6, 11) === 36 && f.pathSum(9, 7) === 14, "path after");
console.log("all tests pass");
Variant: path maximum with binary lifting
Store the maximum edge weight on each jump next to the jump target. Verified against brute force on random trees.
import random
def build(n, parent, w): # parent[root] = root, w[v] = weight of edge v-parent
depth = [0] * n
for v in range(n): # parents have smaller ids in the test trees
if parent[v] != v:
depth[v] = depth[parent[v]] + 1
log = max(1, (n - 1).bit_length())
up, mx = [parent[:]], [[w[v] if parent[v] != v else 0 for v in range(n)]]
for k in range(1, log):
pu, pm = up[-1], mx[-1]
up.append([pu[pu[v]] for v in range(n)])
mx.append([max(pm[v], pm[pu[v]]) for v in range(n)])
return depth, up, mx
def path_max(u, v, depth, up, mx):
best = 0
if depth[u] < depth[v]:
u, v = v, u
d = depth[u] - depth[v]
for k in range(len(up)):
if d >> k & 1:
best, u = max(best, mx[k][u]), up[k][u]
if u == v:
return best
for k in range(len(up) - 1, -1, -1):
if up[k][u] != up[k][v]:
best = max(best, mx[k][u], mx[k][v])
u, v = up[k][u], up[k][v]
return max(best, mx[0][u], mx[0][v])
random.seed(8)
for _ in range(100):
n = random.randint(1, 30)
parent = [0] + [random.randrange(i) for i in range(1, n)]
w = [0] + [random.randint(1, 100) for _ in range(1, n)]
depth, up, mx = build(n, parent, w)
for _ in range(30):
a, b = random.randrange(n), random.randrange(n)
x, y, best = a, b, 0 # brute force: climb the deeper node step by step
while x != y:
if depth[x] >= depth[y]:
best, x = max(best, w[x]), parent[x]
else:
best, y = max(best, w[y]), parent[y]
assert path_max(a, b, depth, up, mx) == best
print("path max ok")
Real-world uses
- Version control.
git merge-basefinds a best common ancestor of two commits. The commit history is a DAG, not a tree, so Git does not use binary lifting: it walks both histories in date or generation order, "painting" commits reachable from each side. Since Git 2.18 the commit-graph file stores generation numbers (a depth-like topological level) so the walk can stop early — exactly the role depth plays in the "equalise depths" step here. For tree-shaped histories (or a single branch), the problem is literally LCA. - Blockchains. Bitcoin Core's
CBlockIndexstores apskippointer to an earlier ancestor, chosen by a deterministic function of the height, soGetAncestor(h)takes hops instead of walking back block by block. It is a skip-list flavour of jump pointers on a long chain with forks. - Compilers. The dominator tree's "nearest common dominator" is an LCA; the Cooper–Harvey–Kennedy dominance algorithm repeatedly intersects two dominator chains by walking up with postorder numbers — the naive LCA, which is fast because dominator trees are shallow in practice. SSA construction and loop analysis query dominance with tin/tout intervals ( dominates iff 's interval nests inside 's), the same ancestor test as on this page.
- Documents and UIs. The DOM
Range.commonAncestorContaineris the LCA of the range's endpoints; editors compute it on every selection change. Trees are shallow, so the naive climb is used. - Bioinformatics. "Most recent common ancestor" queries on phylogenetic trees with millions of leaves (taxonomy databases, read classification tools that assign a DNA read to the LCA of all taxa it matches) use RMQ-based LCA for speed.
- Networking. Routing and multicast trees use LCA to find where two paths diverge; hierarchical name systems such as DNS are trees where the longest common suffix of two names is their LCA.
- Databases. Hierarchical data stored with the nested set model (each row has
lft/rgtcolumns) is precisely the tin/tout flattening: "all descendants of " becomesWHERE lft BETWEEN x.lft AND x.rgt, served by a B-tree index range scan. See also the relational model.
Pitfalls & edge cases
- Recursion depth. A path of nodes overflows Python's default recursion limit and can overflow native stacks. Use BFS for parents/depths and an explicit stack for the Euler tour.
- Too few levels. must satisfy . Using instead of fails on paths of exactly nodes.
(n - 1).bit_length()(at least 1) is safe. - Root's parent. Setting it to makes
up[k-1][-1]index the last element in Python (silently wrong) and crash elsewhere. Set it to the root itself, and check explicitly inkthAncestor. - Forgetting the check after lifting returns the parent of the true LCA when one node is an ancestor of the other.
- Jumping when ancestors are equal in the second loop overshoots to a common ancestor above the LCA. The rule is: jump only when they differ.
- Euler tour length. The vertex-visit tour has entries; the entry/exit tour has . Mixing them breaks index arithmetic.
- Ties in the RMQ. Compare depths, not node ids; returning the position instead of the node requires mapping back.
- Path sums with node values. Forgetting (it is subtracted twice). For edge weights, do not add it.
- Disconnected input / forests. Add a virtual root connected to each component's root, or run per component and answer "no LCA" across components.
- 1-indexed problem input. CSES and Codeforces number nodes from 1. Convert once at input time.
- Overflow. Path sums of values up to need 64-bit integers.
- up to on functional graphs. Need 30 levels, not levels: the walk can cycle, so is not bounded by .
Variations
- Jump pointers with amortised extra space (skew-binary jumps). Each node stores only its parent and one "jump" pointer chosen so that jumps follow a skew-binary pattern; -th ancestor and LCA are with memory, and nodes can be added as leaves online (Myers 1983; popularised in contest circles as the " memory binary lifting"). Useful when the tree grows online and memory is too much.
- Level ancestor in : the ladder algorithm (long-path decomposition extended upward, plus jump pointers) gives preprocessing and -th ancestor queries; with micro-trees, preprocessing (Bender & Farach-Colton 2004).
- Virtual (auxiliary) trees: given marked nodes, sort them by , add the LCAs of adjacent pairs, and you get a compressed tree of at most nodes preserving all pairwise LCAs. Used to answer many queries each touching a small node set, in per query.
- Binary lifting for "first ancestor with value ": store per jump and descend greedily, as in the LCA loop.
- Binary lifting on the answer (parallel to binary search): "the largest such that a monotone predicate holds after steps" — the top-down jump loop is a binary search that never needs random access, used in Fenwick-tree descents and in suffix-array LCP calculations.
- Path updates and path queries interleaved: neither binary lifting nor flattening suffices; use Heavy-Light Decomposition () or link-cut trees ( amortised).
- Tarjan's offline LCA as an introduction to union-find on trees; the same DFS-and-merge pattern underlies small-to-large merging in the next lesson.
Practice ladder
Each problem is described in my own words. Solutions are Python and are run as part of this page's checks against brute force.
1. Lowest Common Ancestor of a Binary Search Tree (LeetCode 235) — Easy. Teaches that the BST ordering finds the LCA without parent pointers: go left while both keys are smaller, right while both are larger.
Hint
The LCA is the first node whose key lies between the two targets (inclusive).
2. Lowest Common Ancestor of a Binary Tree (LeetCode 236) — Medium. A single query on a pointer-based tree. Teaches the one-pass recursive LCA (return the node if found in both subtrees).
Hint
Return the current node if it is or ; otherwise recurse left and right; if both return non-null, the current node is the LCA.
3. Company Queries I (CSES 1687) — Easy/Medium. -th boss of an employee. Teaches the jump table and the case.
Hint
Bosses have smaller ids in this problem, so parents can be read in order. Answer when exceeds the depth.
Solution
import random
def solve(n: int, boss: list[int], queries: list[tuple[int, int]]) -> list[int]:
# boss[i] for employees 2..n (1-indexed); employee 1 is the root
LOG = max(1, n.bit_length())
up = [[0] * (n + 1) for _ in range(LOG)] # 0 = "no such boss"
for i in range(2, n + 1):
up[0][i] = boss[i - 2]
for k in range(1, LOG):
for v in range(1, n + 1):
up[k][v] = up[k - 1][up[k - 1][v]]
out = []
for x, k in queries:
b = 0
while k and x:
if k & 1:
x = up[b][x] if b < LOG else 0
k >>= 1
b += 1
out.append(x if x else -1)
return out
random.seed(1)
for _ in range(200):
n = random.randint(1, 30)
boss = [random.randint(1, i - 1) for i in range(2, n + 1)]
qs = [(random.randint(1, n), random.randint(1, 40)) for _ in range(20)]
exp = []
for x, k in qs:
for _ in range(k):
x = boss[x - 2] if x > 1 else -1
if x == -1:
break
exp.append(x)
assert solve(n, boss, qs) == exp
print("ok")
Using 0 as a sentinel "beyond the root" node with avoids clamping and makes "no such boss" fall out naturally. .
4. Kth Ancestor of a Tree Node (LeetCode 1483) — Hard (on LeetCode). The same as problem 3 as a class API. Teaches packaging binary lifting.
Hint
Build up in the constructor (levels up to ); getKthAncestor jumps per set bit and returns when it falls off.
5. Company Queries II (CSES 1688) — Medium. LCA of two employees. Teaches the full LCA routine.
Hint
Exactly TreeLCA.lca, with 1-indexed input converted.
6. Distance Queries (CSES 1135) — Medium. Distances between pairs of nodes. Teaches depth arithmetic with LCA.
Hint
.
Solution
import random
from collections import deque
def solve(n: int, edges: list[tuple[int, int]], queries: list[tuple[int, int]]) -> list[int]:
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b); adj[b].append(a)
par, dep = [0] * n, [0] * n
seen = [False] * n; seen[0] = True
dq = deque([0])
while dq:
x = dq.popleft()
for y in adj[x]:
if not seen[y]:
seen[y] = True; par[y] = x; dep[y] = dep[x] + 1; dq.append(y)
LOG = max(1, (n - 1).bit_length())
up = [par]
for _ in range(1, LOG):
up.append([up[-1][up[-1][v]] for v in range(n)])
def lca(u, v):
if dep[u] < dep[v]:
u, v = v, u
d = dep[u] - dep[v]
for k in range(LOG):
if d >> k & 1:
u = up[k][u]
if u == v:
return u
for k in range(LOG - 1, -1, -1):
if up[k][u] != up[k][v]:
u, v = up[k][u], up[k][v]
return up[0][u]
return [dep[a] + dep[b] - 2 * dep[lca(a, b)] for a, b in queries]
def bfs_dist(n, edges, s):
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b); adj[b].append(a)
d = [-1] * n; d[s] = 0
dq = deque([s])
while dq:
x = dq.popleft()
for y in adj[x]:
if d[y] < 0:
d[y] = d[x] + 1; dq.append(y)
return d
random.seed(2)
for _ in range(100):
n = random.randint(1, 25)
edges = [(random.randrange(i), i) for i in range(1, n)]
qs = [(random.randrange(n), random.randrange(n)) for _ in range(15)]
assert solve(n, edges, qs) == [bfs_dist(n, edges, a)[b] for a, b in qs]
print("ok")
.
7. Subtree Queries (CSES 1137) — Medium. Point value changes and subtree sums. Teaches flattening with tin/tout plus a Fenwick tree.
Hint
FlatTree.subtree above. For a value assignment, add the difference.
8. Path Queries (CSES 1138) — Medium. Point value changes and root-to-node path sums. Teaches the dual trick: range add over a subtree, point query.
Hint
FlatTree.root_sum above: a change at is a range add on .
9. Planets Queries I (CSES 1750) — Medium. Each planet has one teleporter; find where you end after teleports, up to . Teaches binary lifting on a functional graph.
Hint
30 levels of up[k][x]; jump per set bit of .
Solution
import random
def solve(succ: list[int], queries: list[tuple[int, int]]) -> list[int]:
LOG = 30
up = [succ[:]]
for _ in range(1, LOG):
prev = up[-1]
up.append([prev[prev[x]] for x in range(len(succ))])
out = []
for x, k in queries:
b = 0
while k:
if k & 1:
x = up[b][x]
k >>= 1
b += 1
out.append(x)
return out
assert solve([2, 3, 4, 1, 0, 6, 5, 0], [(0, 1), (0, 5), (7, 10), (5, 7), (3, 13)]) == [2, 4, 0, 6, 1]
random.seed(3)
for _ in range(100):
n = random.randint(1, 15)
succ = [random.randrange(n) for _ in range(n)]
qs = [(random.randrange(n), random.randint(0, 200)) for _ in range(20)]
exp = []
for x, k in qs:
for _ in range(k):
x = succ[x]
exp.append(x)
assert solve(succ, qs) == exp
print("ok")
with .
10. Counting Paths (CSES 1136) — Medium/Hard. Many paths are given; report for each node how many paths pass through it. Teaches the difference-on-tree trick.
Hint
For each path with : diff[a] += 1; diff[b] += 1; diff[w] -= 1; diff[parent(w)] -= 1 (skip the last if is the root). Then each node's answer is the sum of diff over its subtree, computed bottom-up.
Solution
import random
from collections import deque
def solve(n: int, edges: list[tuple[int, int]], paths: list[tuple[int, int]]) -> list[int]:
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b); adj[b].append(a)
par, dep, order = [-1] * n, [0] * n, []
seen = [False] * n; seen[0] = True
dq = deque([0])
while dq:
x = dq.popleft(); order.append(x)
for y in adj[x]:
if not seen[y]:
seen[y] = True; par[y] = x; dep[y] = dep[x] + 1; dq.append(y)
def lca(u, v): # naive climb is enough for the test sizes
while dep[u] > dep[v]: u = par[u]
while dep[v] > dep[u]: v = par[v]
while u != v: u, v = par[u], par[v]
return u
diff = [0] * n
for a, b in paths:
w = lca(a, b)
diff[a] += 1; diff[b] += 1; diff[w] -= 1
if par[w] != -1:
diff[par[w]] -= 1
for x in reversed(order): # children before parents
if par[x] != -1:
diff[par[x]] += diff[x]
return diff
random.seed(4)
for _ in range(100):
n = random.randint(1, 20)
edges = [(random.randrange(i), i) for i in range(1, n)]
paths = [(random.randrange(n), random.randrange(n)) for _ in range(10)]
par = [-1] + [a for a, _ in sorted(edges, key=lambda e: e[1])]
cnt = [0] * n
for a, b in paths: # brute force: mark the path explicitly
anc_a = []
x = a
while x != -1:
anc_a.append(x); x = par[x]
on_path, x = set(), b
while x not in anc_a:
on_path.add(x); x = par[x]
for y in anc_a[:anc_a.index(x) + 1]:
on_path.add(y)
for y in on_path:
cnt[y] += 1
assert solve(n, edges, paths) == cnt
print("ok")
with binary-lifting LCA; the subtree accumulation is .
11. Tree Queries (Codeforces 1328E) — Medium/Hard. Decide whether some root-to-node path passes within distance 1 of every vertex in a query set. Teaches replacing each vertex by its parent and testing ancestry with tin/tout.
Hint
Replace each query vertex by its parent (the root stays). Take the deepest one, ; the answer is yes iff every replaced vertex is an ancestor of .
12. Misha, Grisha and Underground (Codeforces 832D) — Medium/Hard. Three stations; choose roles to maximise the overlap of two paths. Teaches path-intersection lengths from distances: .
Hint
Try all three choices of the shared endpoint ; compute the overlap with the formula using LCA distances.
13. Minimum spanning tree for each edge (Codeforces 609E) — Hard. For each edge, the cheapest spanning tree containing it. Teaches path maximum by binary lifting over an MST.
Hint
Build one MST (Kruskal). For an edge not in it, the answer is ; the path max comes from the variant above.
14. Minimum Edge Weight Equilibrium Queries in a Tree (LeetCode 2846) — Hard. Weights are 1..26; make all edges on a path equal with the fewest changes. Teaches root prefix count vectors combined with LCA.
Hint
Keep, for each node, the count of each weight on its root path. The path's count for weight is ; the answer is path length minus the largest count.
15. Planets Queries II (CSES 1160) — Hard. Minimum teleports from to in a functional graph, or . Teaches combining binary lifting with the cycle-and-tail structure of functional graphs.
Hint
Find cycles and each node's distance to its cycle. If is on the tail path from , use depths and a -th successor check; if is on the cycle that 's tail reaches, add the distance to the cycle and the distance around it; otherwise .
Common mistakes & interview follow-ups
"What if the tree is a binary search tree?" Use the ordering: the LCA is the first node on the root path whose key lies between the two keys. , no preprocessing.
"What if you only have parent pointers and no root?" Climb from both nodes to compute depths, equalise, climb together: time, extra space. Or the "two pointers switching lists" trick from intersecting linked lists: walk and ; both pointers have walked the same total distance when they first coincide, and they coincide at the LCA after at most steps.
"How would you handle queries?" Euler tour plus sparse table: per query, two independent memory reads. Or offline Tarjan if memory is tight.
"The tree changes (new leaves are added)." Binary lifting handles leaf insertion online: a new leaf's row is computed from its parent's in . Re-rooting or cutting edges needs link-cut trees or Euler-tour trees.
"Sum on a path with updates?" Point updates and path sums: flatten and use the root-sum Fenwick trick plus LCA, . Path updates with path queries: heavy-light decomposition.
"Why is the second loop top-down and not bottom-up?" It is a binary search over the climb distance; trying the largest powers first finds the maximal climb that keeps the nodes distinct. Bottom-up would commit to small jumps that might make larger ones impossible to represent.
Common mistakes: recursion on deep trees; one too small; root parent ; skipping the check; jumping when ancestors are equal; forgetting in node-valued path sums; 32-bit overflow.
Quick quiz
- In the example tree, what are and ?
Answer
(). ().
- Why must the second loop skip a jump when ?
Answer
Equal ancestors are a common ancestor, but not necessarily the lowest; jumping could overshoot. The loop's invariant is that (both strictly below the LCA), and only jumps that preserve it are taken. At the end the LCA is their common parent.
- Which node is shallowest between positions 3 and 8 of the Euler sequence
0 1 3 5 6 5 3 1 4 11 4 1 0 …, and which query does that answer?
Answer
Positions 3..8 hold 5, 6, 5, 3, 1, 4; the shallowest is node 1 (depth 1). and , so it answers .
- Write the path-sum formula for node values and explain the last term.
Answer
with . Subtracting twice removes too, but is on the path, so it is added back once.
- On a functional graph with and , how many levels does the jump table need?
Answer
levels — the walk can cycle, so is not bounded by . (Alternatively reduce modulo the cycle length after reaching the cycle.)
Further reading / sources
- cp-algorithms: Lowest Common Ancestor — O(sqrt(N)) and O(log N) with O(N) preprocessing, LCA — Binary Lifting, LCA — Farach-Colton and Bender, LCA — Tarjan's off-line algorithm.
- R. E. Tarjan, "Applications of Path Compression on Balanced Trees", Journal of the ACM 26(4):690–715, 1979. DOI 10.1145/322154.322161.
- D. Harel & R. E. Tarjan, "Fast Algorithms for Finding Nearest Common Ancestors", SIAM Journal on Computing 13(2):338–355, 1984. DOI 10.1137/0213024.
- B. Schieber & U. Vishkin, "On Finding Lowest Common Ancestors: Simplification and Parallelization", SIAM Journal on Computing 17(6):1253–1262, 1988.
- M. A. Bender & M. Farach-Colton, "The LCA Problem Revisited", LATIN 2000, LNCS 1776, pp. 88–94; and "The Level Ancestor Problem Simplified", Theoretical Computer Science 321(1):5–12, 2004.
- E. W. Myers, "An applicative random-access stack", Information Processing Letters 17(5):241–248, 1983 — skew-binary jump pointers.
- A. Laaksonen, Competitive Programmer's Handbook, chapter 18 (tree queries: ancestors, subtrees, paths, LCA).
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 3rd ed., Problem 21-3 (Tarjan's off-line LCA) and Chapter 21 (disjoint sets).
- Git documentation:
git merge-baseand the commit-graph format (generation numbers); Bitcoin Core source,src/chain.h(CBlockIndex::pskip).
Prev: Sparse Tables, Sqrt Decomposition & Mo's Algorithm · Next: Heavy-Light & Centroid Decomposition
Related: Module 3 — Trees · Trees (Overview) · Binary Trees & Traversals · Fenwick Trees · Segment Trees in Depth · Graphs · Advanced Data Structures · DSA: Zero to Mastery