Somewhat Frequent
0/26

# Binary Jumping

Authors: Benjamin Qi, Neo Wang, Qi Wang

Introduces the problems of finding level ancestors in a tree and computing the lowest common ancestors.

## Binary Jumping

Focus Problem – read through this problem before continuing!

### Pro Tip

Binary jumping is more commonly referred to as "binary lifting."

### Solution

To solve this problem, we can use a standard binary lifting implementation where jmp(int x, int d) corresponds to the $d$-th ancestor of $x$.

In our jmp(int x, int d) if our final value of $x$ is $0$, then such a node does not exist and we can simply return $-1$. This is because the lowest number a node can be is $1$ (the root of the tree).

In our implementation, we test if we jump in powers of two by using the $\&$ operator. If the $i$th bit on the right is toggled, then we jump. For example, a jump of $13$ would correspond to the binary number $1101$. We would jump 3 times on bits $0, 2, 3$ (in that order) counting from the right.

Illustration of the jump method

To calculate the rows required for the int up[MS][MX] array, use the formula $\lceil \log_2{N} \rceil$ which in our case simplifies to $\lceil \log_2{(2\cdot 10^5)}\rceil = 18$.

### Pro Tip

It never hurts to add additional rows - or columns, depending on your implementation - (as long as it's reasonable)!

C++

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)#define FORE(i, a, b) for(int i = (a); i <= (b); i++)#define F0R(i, a) for(int i = 0; i < (a); i++)#define trav(a, x) for (auto& a : x)
int N, Q;

### Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsBinary Jumping
CSESNormal
Show TagsFunctional Graph
POINormal
CFNormal
Baltic OINormal
Baltic OINormal
PlatHard
Show TagsBinary Jumping
Baltic OIVery Hard

## Lowest Common Ancestor

Focus Problem – read through this problem before continuing!

Focus Problem – read through this problem before continuing!

### Solution (Company Queries II)

Resources
CPH

brief description

Benq

alternative implementation

To find $\textrm{lca}(a, b)$, we can first lift the lower node of $a$ and $b$ to the same depth as the other. Then, we lift both nodes up decrementally. At the end, the parent of either node is the LCA of the two.

C++

 Code Snippet: Benq Template (Click to expand)
int N, Q, T = 1;int depth;int up;vi adj;
void dfs(int v) {	FOR(i, 1, 20) {		up[v][i] = up[up[v][i-1]][i-1];

### Alternative Solution (Company Queries II)

As mentioned in the Euler Tour Technique module, let $\texttt{st}, \texttt{en}, \texttt{up}$ be the time-in, time-out, and ancestor table for all nodes in the tree.

These can be filled with a DFS traversal. $\texttt{up}$ can be generated because DFS allows the ancestors to be filled first before traversing the current node.

With this information, we can declare node $a$ an ancestor of $b$ if $\texttt{st}[a] \le \texttt{st}[b]$ and $\texttt{en}[a] \ge \texttt{en}[b]$.

We know that if $a$ is an ancestor of $b$ or $b$ is an ancestor of $a$, the answer will be $a$ or $b$ respectively. Otherwise, we lift one of the nodes up (in this case, $a$) decrementally while it is not the ancestor of $b$. Therefore, if $\texttt{up}[a][i]$ is not an ancestor of $b$, then we can set $a$ to be $\texttt{up}[a][i]$, else, we will decrement $i$ and try to find a lower common ancestor. Afterwards, our answer is the parent of $a$.

C++

 Code Snippet: Benq Template (Click to expand)
int N, Q, T = 1;vi st, en;int up;vi adj;
void dfs(int v, int p) {	st[v] = T++;	up[v] = p;
Resources
cp-algo

### Solution (Distance Queries)

Find LCA of node $a$ and $b$ as described above. Then, the distance between the two nodes would be the $\texttt{depth}[a] + \texttt{depth}[b] - 2 \cdot \texttt{depth}[\textrm{lca}(a, b)]$.

C++

 Code Snippet: Benq Template (Click to expand)
int N, Q, T = 1;int depth;int up;vi adj;
void dfs(int v) {	FOR(i, 1, 20) {		up[v][i] = up[up[v][i-1]][i-1];

### Problems

#### USACO

StatusSourceProblem NameDifficultyTags
PlatEasy
Show TagsLCA
PlatNormal
Show TagsLCA
PlatHard
Show TagsLCA
PlatHard
Show TagsDiameter
PlatHard
Show TagsLCA
PlatVery Hard
Show TagsLCA

#### General

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsBinary Jumping
CFNormal
Show TagsLCA
Baltic OINormal
CFNormal
Show TagsLCA
CSANormal
Show TagsLCA
CFNormal
Show TagsLCA
DMOJNormal
Show TagsLCA
TLXHard
Show TagsLCA
TLXHard
Show TagsLCA

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

figure out a better way to order these, difficulties aren't really accurate

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!