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 – try your best to solve 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 -th ancestor of .
In our jmp(int x, int d)
if our final value of is , then such a node
does not exist and we can simply return . This is because the lowest number
a node can be is (the root of the tree).
In our implementation, we test if we jump in powers of two by using the operator. If the th bit on the right is toggled, then we jump. For example, a jump of would correspond to the binary number . We would jump 3 times on bits (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
which in our case simplifies to
.
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 | |||
CSES | Normal | Show Tags2P, Binary Jumping, Binary Search | |||
POI | Normal | ||||
CF | Normal | ||||
Baltic OI | Normal | ||||
Baltic OI | Normal | ||||
Platinum | Hard | Show TagsBinary Jumping | |||
Baltic OI | Very Hard |
Lowest Common Ancestor
Focus Problem – try your best to solve this problem before continuing!
Focus Problem – try your best to solve this problem before continuing!
Solution (Company Queries II)
Resources | ||||
---|---|---|---|---|
CPH | Brief description/solution | |||
SansPapyrus683 | Alternative implementation |
To find , we can first lift the lower node of and 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 be the time-in, time-out, and ancestor table for all nodes in the tree.
These can be filled with a DFS traversal. can be generated because DFS allows the ancestors to be filled first before traversing the current node.
With this information, we can declare node an ancestor of if and .
We know that if is an ancestor of or is an ancestor of , the answer will be or respectively. Otherwise, we lift one of the nodes up (in this case, ) decrementally while it is not the ancestor of . Therefore, if is not an ancestor of , then we can set to be , else, we will decrement and try to find a lower common ancestor. Afterwards, our answer is the parent of .
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;
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.
C++
Code Snippet: Benq Template (Click to expand)#include <bits/stdc++.h>using namespace std;#pragma GCC optimize("O3")#pragma regionusing ll = long long;using db = long double; // or double, if TL is tight
Resources | ||||
---|---|---|---|---|
cp-algo |
Optional: Improvements
Solution (Distance Queries)
Find LCA of node and as described above. Then, the distance between the two nodes would be the .
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 | |
---|---|---|---|---|---|
Platinum | Easy | Show TagsLCA | |||
Platinum | Normal | Show TagsLCA | |||
Old Gold | Normal | Show TagsBinary Jumping, Euler Tour, Small to Large | |||
Platinum | Hard | Show TagsLCA | |||
Platinum | Hard | Show TagsDiameter | |||
Platinum | Hard | Show TagsLCA | |||
Platinum | 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 | |||
CF | Normal | Show TagsLCA | |||
CSA | Normal | Show TagsLCA | |||
CF | Normal | Show TagsLCA | |||
Back to School | Normal | Show TagsLCA | |||
Google Kickstart | Hard | Show TagsBinary Jumping, DFS, LCA | |||
CF | Hard | Show TagsBinary Jumping, LCA | |||
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!