Binary Lifting (Gold) Intro

When you get to a certain point in programming contests, you will almost certainly hit problems on trees. Binary lifting (also known as binary jumping) is one of the most powerful algorithms you can learn to traverse trees, and when put to use with other algorithms (preorder DFS, Euler tour, and more), you can solve a whole array of problems that would otherwise be impossible. Unfortunately, many of the resources available as of now describe the method in one or two sentences and then provide a large block of code, prompting many people to memorize the code without actually understanding what is going on.

This will be a three part series covering the basics, each part roughly described as follows:

• Part 1: Dissecting the Logic Underlying Binary Lifting and Finding the kth Ancestor of a Node

• Part 2: Applying Binary Lifting to Find LCA of Two Nodes

• Part 3: Applying Binary Lifting to Find Node to Node Distance

Then, a fourth part, if made, would cover more advanced applications of binary lifting when used in conjunction with other algorithms.

In all, the goal is to teach binary lifting code and applications in steps and then put it all together.