# 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!

### Tutorial

Resources | |||
---|---|---|---|

CPH | |||

AryanshS | |||

SecondThread |

### 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

Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|

CSES | Easy | ## Show TagsBinary Jumping | |||||||

CSES | Normal | ## Show TagsFunctional Graph | |||||||

POI | Normal | ||||||||

CF | Normal | ||||||||

Baltic OI | Normal | ||||||||

Baltic OI | Normal | ||||||||

Plat | Hard | ## Show TagsBinary Jumping | |||||||

Baltic OI | Very 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[200005];int up[200005][20];vi adj[200005];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[200005][20];vi adj[200005];void dfs(int v, int p) {st[v] = T++;up[v][0] = 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[200005];int up[200005][20];vi adj[200005];void dfs(int v) {FOR(i, 1, 20) {up[v][i] = up[up[v][i-1]][i-1];

### Problems

#### USACO

Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|

Plat | Easy | ## Show TagsLCA | |||||||

Plat | Normal | ## Show TagsLCA | |||||||

Plat | Hard | ## Show TagsLCA | |||||||

Plat | Hard | ## Show TagsDiameter | |||||||

Plat | Hard | ## Show TagsLCA | |||||||

Plat | Very Hard | ## Show TagsLCA | |||||||

#### General

Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|

CF | Easy | ## Show TagsBinary Jumping | |||||||

CF | Normal | ## Show TagsLCA | |||||||

Baltic OI | Normal | ||||||||

CF | Normal | ## Show TagsLCA | |||||||

CSA | Normal | ## Show TagsLCA | |||||||

CF | Normal | ## Show TagsLCA | |||||||

DMOJ | Normal | ## Show TagsLCA | |||||||

TLX | Hard | ## Show TagsLCA | |||||||

TLX | Hard | ## Show TagsLCA | |||||||

### This section is not complete.

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

### Module Progress:

### 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!