Binary Lifting

Binary lifting preprocesses ancestor jumps of lengths 1,2,4,8,… so a long climb becomes a small number of jumps. It answers K-th ancestor queries and speeds up LCA from O(tree height) to O(log N), even for a path-shaped tree. The tradeoff is an O(N log N) table built once.

This is a static-tree technique: the code assumes the tree and root stay fixed after preprocessing. You will derive the doubling recurrence, use the set bits of K to climb exactly K edges, and find LCA by jumping both endpoints while carefully staying below their first shared ancestor.

Prerequisites: Lowest Common Ancestor (Basic Method); binary representation and powers of two.

Build the idea

1. 1. Define the ancestor table

   Let up[v][j] be the ancestor reached by moving 2^j parent edges upward from v, or 0 if it does not exist. Column 0 stores the immediate parent. A jump of length 2^j is two jumps of length 2^(j−1), so up[v][j]=up[up[v][j−1]][j−1]. Initialize row 0 to all zeroes: once a jump reaches the sentinel, every later jump stays there safely.

   On path 1–2–3–4–5–6–7–8 rooted at 1, up[8][0]=7, up[8][1]=6, and up[8][2]=4. The 8-edge ancestor does not exist. Use enough columns to represent jumps needed for N vertices; the program computes LOG dynamically instead of assuming one contest-specific limit.

2. 2. Build smaller jumps before larger ones

   BFS first supplies depths and immediate parents. Then build the table column by column: every entry in column j depends only on column j−1, which is already finished. This makes the dependency explicit and avoids relying on a particular vertex-number ordering. Labels need not be parent-before-child.

   The allocated table has N+1 rows and LOG columns indexed 0..LOG−1. Depth uses edge count and starts at zero. A connected one-vertex tree still allocates at least one column; its parent is 0.

3. 3. Answer the K-th ancestor query

   Write K in binary. For example 5=4+1=101₂, so from vertex 8, jump four edges to 4 and one edge to 3. The order of these upward jumps does not affect the final ancestor, provided the total length is exactly K. The loop examines each bit j and uses up[v][j] when that bit is set.

   K=0 returns v itself. If K>depth[v], the requested ancestor does not exist; return 0 immediately. This test also makes large K values safe without indexing beyond available columns. The implementation reads K as long long but stores vertex labels and depths as int.

4. 4. Level the LCA endpoints

   As in the basic method, raise the deeper endpoint by its depth difference. Binary lifting performs this in O(log N). If the endpoints now match, return that vertex: one original endpoint was an ancestor of the other.

   Otherwise consider jump sizes from largest to smallest. If up[U][j] and up[V][j] differ, move both endpoints to those ancestors. The move is safe because two equal-depth vertices already at or above their LCA would have the same ancestor at that level; unequal destinations therefore remain strictly below the LCA. If the destinations agree, do not jump: that would reach or overshoot the meeting point.

5. 5. Finish one edge below the answer

   After all jump sizes have been considered, U and V are distinct but their immediate parents agree. Return up[U][0]. For a concrete example, root the tree with edges (1,2), (2,3), (3,4), (2,5), (5,6), (6,7). For LCA(4,7), first raise 7 to 6, giving equal-depth vertices 4 and 6. Their 2-edge ancestors both equal 2, so that jump is skipped. Their 1-edge ancestors are 3 and 5, so take that jump. Now both parents equal 2, the answer.

   The doubling table speeds up movement, but the proof is still the basic LCA proof: level the endpoints, stay below their first meeting, then return its parent. Rebuilding is necessary after structural edits or changing the chosen root.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,root,queries;
    cin>>n>>root>>queries;
    vector<vector<int>>graph(n+1);
    for(int i=0;i<n-1;++i){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    // Allocate enough powers-of-two jump columns for every possible tree depth.
    int LOG=1;
    while((1LL<<LOG)<=n){
        ++LOG;
    }
    // up[v][j] is the 2^j-th ancestor; row 0 remains the missing-vertex sentinel.
    vector<vector<int>>up(n+1,vector<int>(LOG,0));
    vector<int>depth(n+1,0);
    queue<int>q;
    q.push(root);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int next:graph[v]){
            if(next!=up[v][0]){
                up[next][0]=v;
                depth[next]=depth[v]+1;
                q.push(next);
            }
        }
    }
    // Column j depends only on the completed column j-1.
    for(int j=1;j<LOG;++j){
        for(int v=1;v<=n;++v){
            up[v][j]=up[up[v][j-1]][j-1];
        }
    }
    auto kth=[&](int v,long long k){
        if(k>depth[v]){
            return 0; // No ancestor above the root.
        }
        // The set bits of k add up to exactly the desired climbing distance.
        for(int j=0;j<LOG;++j){
            if((k>>j)&1LL){
                v=up[v][j];
            }
        }
        return v;
    };
    auto lca=[&](int u,int v){
        if(depth[u]<depth[v]){
            swap(u,v);
        }
        // First level the endpoints; an equal result already is their LCA.
        u=kth(u,depth[u]-depth[v]);
        if(u==v){
            return u;
        }
        for(int j=LOG-1;j>=0;--j){
            // Unequal destinations stay below the LCA, so this jump cannot overshoot it.
            if(up[u][j]!=up[v][j]){
                u=up[u][j];
                v=up[v][j];
            }
        }
        return up[u][0];
    };
    while(queries--){
        string type;
        cin>>type;
        if(type=="K"){
            int v;
            long long k;
            cin>>v>>k;
            cout<<kth(v,k)<<'\n';
        }
        else{ // Input operation L u v asks for the LCA.
            int u,v;
            cin>>u>>v;
            cout<<lca(u,v)<<'\n';
        }
    }
}

Complexity analysis

Preprocessing takes O(N log N) time and space for the ancestor table; rooting alone is O(N). Each K-th ancestor or LCA query takes O(log N) time and O(1) additional space. Q queries cost O((N+Q) log N) total time.

Example input and output

N root Q, N−1 edges of a valid tree, then Q operations: K v k (k≥0) prints the k-th ancestor or 0 if absent; L u v prints their LCA.

Input

8 1 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
K 8 5
K 8 0
K 8 8
L 6 8
L 1 8
K 1 1000000000

Output

3
8
0
6
1
0

Five steps above 8 reaches 3, zero steps stays at 8, and eight steps exceeds its depth. On a path rooted at 1, the shallower query vertex is the LCA.

Practical applications

Many static LCA queries, K-th ancestors, distances, K-th vertices on paths, and virtual trees. Augment jumps with sums/minima to aggregate values along upward paths; that requires extra tables and an appropriate merge operation.

Check your understanding

What does up[v][j] represent?

Put it into practice

Add a D u v operation returning the distance between two vertices without another traversal.