LCA Jump
(library/graphs/lca-jump.hpp)

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Include: #include "library/graphs/lca-jump.hpp"

LCA Jump

Functions

• init(n): Initializes variables
• gen(root): Generates from $root$, can easily change to vector for forests. Just repeat gen$ for each root. Does this in $\mathcal O(n \log (n))$.
• jump(x, d): Jump $d$ upwards from node $x$ in $\mathcal O(\log n)$.
• lca(x, y): Lowest common ancestor of $x, y$ in $\mathcal O(\log n)$.

Verified with

• verify/yosupo/yosupo-lca-lca-jump.test.cpp
• verify/yukicoder/yukicoder-1326.test.cpp

Code

#pragma once

struct LCAJump {
	int n;
	std::vector<std::vector<int>> par;
	std::vector<std::vector<int>> adj;
	std::vector<int> depth;

	void init(int _n) {
		n = _n;
		int d = 1;
		while ((1 << d) < n) d++;
		par.assign(d, std::vector<int>(n));
		adj.resize(n);
		depth.resize(n);
	}

	void ae(int x, int y) {
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	void gen(int root = 0) {
		par[0][root] = root;
		dfs(root);
	}

	void dfs(int src = 0) {
		for (int i = 1; i < (int)par.size(); i++) {
			par[i][src] = par[i - 1][par[i - 1][src]];
		}
		for (int nxt : adj[src]) {
			if (nxt == par[0][src]) continue;
			depth[nxt] = depth[par[0][nxt] = src] + 1;
			dfs(nxt);
		}
	}

	int jump(int x, int d) {
		for (int i = 0; i < (int)par.size(); i++) {
			if ((d >> i) & 1) {
				x = par[i][x];
			}
		}
		return x;
	}
	
	int lca(int x, int y) {
		if (depth[x] < depth[y]) std::swap(x, y);
		x = jump(x, depth[x] - depth[y]);
		if (x == y) return x;
		for (int i = (int)par.size() - 1; i >= 0; i--) {
			int nx = par[i][x];
			int ny = par[i][y];
			if (nx != ny) x = nx, y = ny;
		}
		return par[0][x];
	}
};

struct LCAJump {
	int n;
	std::vector<std::vector<int>> par;
	std::vector<std::vector<int>> adj;
	std::vector<int> depth;

	void init(int _n) {
		n = _n;
		int d = 1;
		while ((1 << d) < n) d++;
		par.assign(d, std::vector<int>(n));
		adj.resize(n);
		depth.resize(n);
	}

	void ae(int x, int y) {
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	void gen(int root = 0) {
		par[0][root] = root;
		dfs(root);
	}

	void dfs(int src = 0) {
		for (int i = 1; i < (int)par.size(); i++) {
			par[i][src] = par[i - 1][par[i - 1][src]];
		}
		for (int nxt : adj[src]) {
			if (nxt == par[0][src]) continue;
			depth[nxt] = depth[par[0][nxt] = src] + 1;
			dfs(nxt);
		}
	}

	int jump(int x, int d) {
		for (int i = 0; i < (int)par.size(); i++) {
			if ((d >> i) & 1) {
				x = par[i][x];
			}
		}
		return x;
	}
	
	int lca(int x, int y) {
		if (depth[x] < depth[y]) std::swap(x, y);
		x = jump(x, depth[x] - depth[y]);
		if (x == y) return x;
		for (int i = (int)par.size() - 1; i >= 0; i--) {
			int nx = par[i][x];
			int ny = par[i][y];
			if (nx != ny) x = nx, y = ny;
		}
		return par[0][x];
	}
};

Back to top page