Preprocessing Steps

Setting Up for Fast Queries

Before we can ask for the k-th ancestor of a node, we need to do some prep work. This involves pre-calculating and storing ancestor information in a clever way. The goal is to invest time upfront to make future queries incredibly fast. We'll store this information in a structure often called a sparse table or an up table.

This table, let's call it up[i][j], will hold the 2^j-th ancestor of node i. Why powers of two? As we saw before, any number can be represented as a sum of powers of two. By storing these specific ancestors, we can combine them to find any k-th ancestor quickly.

The table will have approximately $N$ rows (one for each node) and $log_2(N)$ columns, because the highest power of two we'd ever need is less than $N$ . This gives us a table of size $O(N \log N)$ .

Building the Table

We fill the table column by column, starting with the easiest case.

Step 1: The Base Case

The first column, where j=0, stores the $2^0$-th ancestor. Since $2^0 = 1$, this is just the immediate parent of each node. We can find all immediate parents by doing a single pass over the tree with a Depth First Search (DFS) or Breadth First Search (BFS).

Step 2: The Recursive Step

Once we know all the immediate parents, we can calculate the ancestors for j=1, which are the $2^1=2$-nd ancestors (the grandparents). The grandparent of a node i is simply the parent of its parent. More generally, the $2^j$-th ancestor of a node is the $2^{j-1}$-th ancestor of its $2^{j-1}$-th ancestor. This gives us a concise recursive relationship.

up[i][j] = up[\,up[i][j-1]\,][j-1]

We can implement this with nested loops. The outer loop iterates through j from 1 to $log_2(N)$ , and the inner loop iterates through each node i.

// Let N be the number of nodes, and LOGN be ceil(log2(N))
// up[N+1][LOGN] is our sparse table, initialized to 0 or -1
// parent[N+1] stores the direct parent of each node

// Step 1: Base case (j=0)
void dfs(int u, int p) {
    parent[u] = p;
    up[u][0] = p;
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
}

// Call dfs(root, 0) to populate parents and the first column

// Step 2: Recursive step
for (int j = 1; j < LOGN; ++j) {
    for (int i = 1; i <= N; ++i) {
        // If the 2^(j-1) ancestor exists
        if (up[i][j-1] != 0) {
            up[i][j] = up[up[i][j-1]][j-1];
        }
    }
}

Time Complexity and Edge Cases

The preprocessing time is dominated by building the sparse table. The initial DFS takes $O(N)$ time. The nested loops run in $O(N \log N)$ time, as we iterate through j up to $\log N$ and i up to $N$ . Therefore, the total time complexity for preprocessing is $O(N \log N)$ . The space complexity is also $O(N \log N)$ to store the table.

This upfront cost of $O(N \log N)$ is a trade-off. It allows us to answer any k-th ancestor query later in just $O(\log N)$ time, which is a significant improvement over the naive $O(N)$ approach for each query.

What happens if a node doesn't have a $2^j$-th ancestor? For example, the 4th ancestor of a node that is only 2 levels below the root. In this case, our recursive formula will eventually try to access an ancestor of the root node. We handle this by setting the parent of the root to a sentinel value like 0 or -1. This signals that we've gone off the top of the tree, and any further ancestor lookups from there will also result in the sentinel value.

With the sparse table fully constructed, we are now ready to answer queries efficiently.

Mastering Binary Lifting

Mastering Binary Lifting

Preprocessing Steps

Setting Up for Fast Queries

Building the Table

Time Complexity and Edge Cases