Hard · Binary Lifting
Understand → Visualise → Practice.
Given each node's parent, return the kth ancestor for every `[node,k]` query or −1.
Precompute up[j][v], the 2ʲ-th ancestor of v. Any k is a sum of powers of two, so the kth ancestor takes at most log k jumps.
up[0] is the parent array. Then up[j][v] = up[j−1][up[j−1][v]], with −1 staying −1.
For each set bit j of k, replace the node by up[j][node].
If the node becomes −1 at any jump, the ancestor does not exist; return −1.
O(n log n) preprocessing and O(log k) per query.
Walking up one parent at a time is O(k) per query, too slow when queries ask for deep ancestors.
Read the full guide first: Fenwick Trees and Segment Trees.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.