Binary Lifting

The core idea of the whole process is intuitive to me so I’ll just leave some implemeational comments on stuff and doubts while writing.

example: company queries 1

• use par as 0 and 1 indexed nodes, this’ll naturally fit in with up going out of bounds
• the essence of the idea is that from u, to up 2k steps, you can go up 2(k-1) steps and then 2**(k-1) steps again

// problem: go up k levels
// tag: bin lift
 
#include <bits/stdc++.h>
using namespace std;
 
int main() {
#define int long long
	int n, q;
	cin >> n >> q;
	vector<vector<int>> g(n + 1);
	for (int i = 2; i <= n; i++) {
		int u;
		cin >> u;
		g[u].push_back(i);
		// now in this I'm given u -> i as input
		// so I could've filled up(u, 0) directly with no
		// dfs but in general if you given bidirectional
		// edges, you would need a "rooting" ( here it's
		// baked into the direction )
		// NOTE: think of what would dfs from 1 do,
		// you need top to down edges
	}
 
	const int D = (int)ceill(log2l(2e5 + 5));
	vector<vector<int>> up(n + 1, vector<int>(D + 1));
 
	auto fill0 = [&](auto &&f, int u, int par) -> void {
		// in this I use the convencion of 0 as no par
		// I've always used -1 but I think this new one is good too
		if (par)
			up[u][0] = par;
		for (int v : g[u])
			if (v != par)
				f(f, v, u);
	};
	fill0(fill0, 1, 0);
 
	for (int d = 1; d <= D; d++) {
		for (int i = 1; i <= n; i++) {
			// go 2^(d-1) up and then 2^(d-1) from there
			// using 0 to represent as NO more up is good implementationally
			// over say -1 as then the 0 naturally flows to up(0) which has
			// all elems 0 naturally
			up[i][d] = up[up[i][d - 1]][d - 1];
		}
	}
 
	auto lift = [&](int u, int k) {
		// the idea being you can represent k as powers of 2 -> binary
		// so going k up can be split into multiple steps of going up
		for (int i = 0; i <= D; i++) {
			if ((k >> i) & 1) {
				u = up[u][i];
			}
		}
		return u;
	};
 
	while (q--) {
		int u, k;
		cin >> u >> k;
		int res = lift(u, k);
		res = res == 0 ? -1 : res;
		cout << res << "\n";
	}
 
#undef int
}

example: company queries 2 ( lca )

• in lca, remember to check if after maching levels, both are same and return if they are.
• why go from D to 0 on finding a jump? I’m applying a greedy and it’s correctness depends on me rejecting what can’t be applied EVER so I would not want to use small jumps only to end up with largers jumps that I cannot use now.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
#define int long long
	int n, q;
	cin >> n >> q;
	vector<vector<int>> g(n + 1);
 
	const int D = (int)ceill(log2l(2e5 + 5));
	vector<vector<int>> up(n + 1, vector<int>(D + 1));
 
	for (int i = 2; i <= n; i++) {
		int u;
		cin >> u;
		g[u].push_back(i);
		up[i][0] = u;
	}
 
	for (int d = 1; d <= D; d++) {
		for (int i = 1; i <= n; i++) {
			up[i][d] = up[up[i][d - 1]][d - 1];
		}
	}
 
	auto lift = [&](int u, int k) {
		for (int i = 0; i <= D; i++) {
			if ((k >> i) & 1) {
				u = up[u][i];
			}
		}
		return u;
	};
 
	vector<int> h(n + 1);
	auto hfill = [&](auto &&f, int u, int par) -> void {
		if (par)
			h[u] = h[par] + 1;
		for (int v : g[u])
			if (v != par)
				f(f, v, u);
	};
	hfill(hfill, 1, 0);
 
	auto lca = [&](int u, int v) {
		if (h[u] < h[v])
			swap(u, v);
		// invariant, h(u) >= h(v)
 
		int diff = h[u] - h[v];
		u = lift(u, diff);
 
		// WARN: remember, otherwise you start from the current lca
		// and the invariant that both are not same used in loop ahead
		// breaks
		if (u == v)
			return u;
 
		// now at same level
		// there MUST exist some k such that
		// moving just one level up from k, they both become same
		// and I have information about the bits of such k by the
		// fact that bit i is 1 if after moving that level up they
		// are both NOT same ( once you reach lca both must be same )
 
		// note that we cannot go in the other direction as it's
		// greedily searching for jumps ( think that we are ruling out
		// suffixes here ), if a suffix is ruled out in the MAX jump case
		// where we had not reduced the distance in any other way
		// that it's ruled out for good
		// if on the other hand many incorrect small jumps can make
		// a later larger jump impossible to make
		// you can even say this is binary search ( the 2^n variation )
		// where I try say 32 then 16 then 8 and so on
		for (int i = D; i >= 0; i--) {
			if (up[u][i] != up[v][i]) {
				u = up[u][i];
				v = up[v][i];
			}
		}
 
		return up[u][0]; // one above is the lca
	};
 
	while (q--) {
		int u, v;
		cin >> u >> v;
		cout << lca(u, v) << "\n";
	}
 
#undef int
}