Tree Lifting — Binary Lifting Idea (Tiny Demo)

Lifting preprocesses “2^k-th ancestor” jumps to answer LCA and path queries in O(log n) after O(n log n) build on static trees.

Try this in Python

LOG = 3  # toy
# up[v][k] would store 2^k-th ancestor; build omitted for brevity
up = [[-1, -1, -1] for _ in range(5)]
print("Store up[v][k] for k in 0..LOG-1; answer queries by jumping powers of two")

Key takeaways

• Requires rooted tree and parent array or DFS order to fill up.
• Dynamic trees need heavier structures (link-cut)—outside intro scope.
• Practice with fixed LOG = max_bit(n).