Binary Jumping

Binary Jumping

Tutorial

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.

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$.

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

Lowest Common Ancestor

Solution (Company Queries II)

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.

Copy
 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$.

Copy
 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;

Alternate Solution II (Company Queries II)

We can also find the LCA of two nodes using the Tarjan's Offline LCA algorithm. By taking advantage of the DFS traversal, we can precompute the answers to the queries through forming subtrees and calculating the common parent with a similar structure as Disjoint-Set Union.

Copy
 Code Snippet: Benq Template (Click to expand)
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")

#pragma region

using ll = long long;
using db = long double;  // or double, if TL is tight

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)]$.

Copy
 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

General