Binary Lifting

Precompute, for every vertex $v$ and every power of two $2^k$, the ancestor $2^k$ levels above it. Any jump of $k$ levels then decomposes into the binary representation of $k$ — $O(\log n)$ per query after $O(n\log n)$ preprocessing.

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

const int LOG = 20;                              // 2^20 > 10^6
vector<array<int, LOG>> up;
 
void build(int root, int n) {
    up.assign(n, {});
    dfs(root, root);                             // sets up[v][0] = parent
    for (int k = 1; k < LOG; k++)
        for (int v = 0; v < n; v++)
            up[v][k] = up[up[v][k-1]][k-1];
}
 
int jump(int v, int k) {
    for (int i = 0; i < LOG && v != -1; i++)
        if (k >> i & 1) v = up[v][i];
    return v;
}

Setting up[root][0] = root makes over-jumping saturate at the root instead of reading garbage — usually what you want.

Carrying an aggregate along

The real power: store any associative aggregate over the $2^k$ edges of each jump.

long long mx[N][LOG];        // maximum edge weight on the 2^k jump
 
mx[v][k] = max(mx[v][k-1], mx[up[v][k-1]][k-1]);

Then a path max, min, sum, gcd, or matrix product is computed by combining $O(\log n)$ precomputed pieces while climbing to the LCA.

long long pathMax(int u, int v) {
    int l = lca(u, v);
    long long res = LLONG_MIN;
    for (int x : {u, v}) {
        int d = depth[x] - depth[l];
        for (int i = 0; i < LOG; i++)
            if (d >> i & 1) { res = max(res, mx[x][i]); x = up[x][i]; }
    }
    return res;
}

Non-invertible aggregates

Sums work with prefix subtraction; max, min and gcd do not. Climb explicitly from both endpoints to the LCA as above, rather than trying f(u) - f(lca).

Beyond trees: functional graphs

Binary lifting needs only a “next” pointer, not a tree. On a functional graph (every vertex has out-degree 1), up[v][k] is the vertex reached after $2^k$ steps, and the same code answers “where am I after $10^{18}$ steps?” in $O(\log k)$.

Application	up[v][0] is
Tree ancestor	parent
Permutation power	$\sigma (v)$
Successor / “next greater” chains	next index
Game state after $k$ moves	the forced move
Sparse table over an array	”jump to the first index outside the current window”

That last one is the basis of the classic “minimum number of intervals to cover a range” solution: precompute for each position the farthest reachable position with one interval, then binary lift to answer coverage queries in $O(\log n)$.

Binary lifting vs the alternatives

Need	Method
LCA only, $O(1)$ query	Euler tour + sparse table
LCA + $k$-th ancestor + path aggregates	binary lifting
Path updates as well as queries	HLD + lazy segment tree
Tree changes (link/cut)	link-cut tree
Level ancestor in $O(1)$	ladder decomposition + jump pointers

Memory

$O(n\log n)$ integers. For $n=10^6$ and $\mathrm{LOG}=20$ that is 80 MB with int — often too much. Options: reduce LOG to $\lceil {\log }_{2}n\rceil$ exactly, switch to the Euler tour method for plain LCA, or use HLD (which is $O(n)$ memory).

See also: LCA · Sparse Table · Functional Graphs