Elevación binaria

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Company Queries I	Fácil	Binary Jumping	en el módulo

Recursos
Fuente	Recurso	Notas
CPH	18.1 - Finding Ancestors
AryanshS	Binary Lifting
SecondThread	Tree Basics - Binary Lifting

Explicación

La elevación binaria consiste en calcular el ancestro $2^k$ -ésimo de cada nodo para todos los valores relevantes de $k$ y guardarlos en una tabla.

Con esa tabla podemos responder de forma eficiente consultas sobre el ancestro $k$ -ésimo de todos los nodos. Esto se debe a que cualquier $k$ se puede descomponer en una suma de potencias de $2$ usando su representación binaria.

Así, en vez de calcular de forma directa, por ejemplo, el ancestro $13$ -ésimo de un nodo, podemos ir al $8$ -ésimo, luego al $4$ -ésimo y después al $1$ -ésimo. Esto da complejidad logarítmica para calcular el $k$ -ésimo padre.

Acá hay una animación de cómo saltamos, por si todavía no queda claro:

Para construir de verdad la tabla de elevación binaria, empezamos con los padres $2^0=1$ -ésimos de cada nodo, que son sus padres directos. Después pasamos a calcular los padres $2^1=2$ -ésimos, usando que el $2$ -ésimo padre se puede obtener como el $1$ -ésimo padre del $1$ -ésimo padre. Con la misma lógica seguimos con $2^2$ , $2^3$ , y así. Paramos cuando $2^n$ es mayor que el tamaño del árbol, porque en ese punto ya estamos con seguridad en la raíz.

Implementación

Complejidad temporal: $\mathcal{O}((N+Q)\log N)$

C++


#include <cmath>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
class Tree {
  private:
	const int log2dist;
	vector<int> par;
	vector<vector<int>> pow2ends;
 
  public:
	Tree(const vector<int> &parents)
	    : log2dist(std::ceil(std::log2(parents.size() + 1))), par(parents.size() + 1),
	      pow2ends(par.size(), vector<int>(log2dist + 1)) {
		par[0] = -1;
		for (int i = 0; i < parents.size(); i++) { par[i + 1] = parents[i]; }
 
		// pow2ends[n][k] guarda el padre 2^k-ésimo del nodo n
		// si no hay padre 2^k-ésimo, el valor es -1
		for (int n = 0; n < par.size(); n++) { pow2ends[n][0] = par[n]; }
		for (int p = 1; p <= log2dist; p++) {
			for (int n = 0; n < par.size(); n++) {
				int halfway = pow2ends[n][p - 1];
				if (halfway == -1) {
					pow2ends[n][p] = -1;
				} else {
					pow2ends[n][p] = pow2ends[halfway][p - 1];
				}
			}
		}
	}
 
	/** @return el k-ésimo padre del nodo n */
	int kth_parent(int n, int k) {
		int at = n;
		// descomponer k en potencias de 2 recorriendo sus bits
		for (int pow = 0; pow <= log2dist; pow++) {
			if ((k & (1 << pow)) != 0) {
				at = pow2ends[at][pow];
				if (at == -1) {
					break;  // parar cuando pasamos la raíz
				}
			}
		}
		return at;
	}
};
 
int main() {
	int employee_num;
	int query_num;
	std::cin >> employee_num >> query_num;
	vector<int> bosses(employee_num - 1);
	for (int &b : bosses) {
		std::cin >> b;
		b--;
	}
 
	Tree tree(bosses);
	for (int q = 0; q < query_num; q++) {
		int employee;
		int dist;
		std::cin >> employee >> dist;
		int kth_boss = tree.kth_parent(--employee, dist);
		cout << (kth_boss != -1 ? kth_boss + 1 : -1) << '\n';
	}
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Planets Queries I	Fácil	Binary Jumping	Solución
CSES	Planets Queries II	Normal	Functional Graph	Solución
CSES	Cyclic Array	Normal	Binary Jumping, Binary Search, 2P	Solución
POI	2010 - Frog	Normal	Binary Jumping, Sliding Window	Solución
CF	Lynyrd Skynyrd	Normal		Solución
Baltic OI	2019 - Valley	Normal		—
Baltic OI	2017 - Toll	Normal		Solución
Platinum	262144	Difícil	Binary Jumping	—
Baltic OI	2015 - Editor	Muy difícil		Solución

Ancestro común más bajo

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Company Queries II	Fácil	LCA	Solución

Recursos
Fuente	Recurso	Notas
CPH	18.3 - LCA Method 1	Descripción breve / solución
SansPapyrus683	LCA Tree	Implementación alternativa

Explicación 1

Para hallar $\textrm{lca}(a, b)$ , primero podemos elevar el nodo más bajo entre $a$ y $b$ hasta la misma profundidad que el otro. Después elevamos ambos nodos de forma decreciente. Al final, el padre de cualquiera de los dos es el LCA.

Implementación

Complejidad temporal: $\mathcal{O}((N+Q)\log N)$

C++


#include <cmath>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
class Tree {
  private:
	const int root = 0;
 
	const vector<vector<int>> &adj;
	const int log2dist;
	vector<int> par;
	vector<vector<int>> pow2ends;
	vector<int> depth;
 
	/** usar DFS para calcular las profundidades y padres de cada nodo */
	void process(int at, int prev) {
		depth[at] = depth[prev] + 1;
		for (int n : adj[at]) {
			if (n != prev) {
				process(n, at);
				par[n] = at;
			}
		}
	}
 
  public:
	Tree(const vector<vector<int>> &adj)
	    : adj(adj), log2dist(std::ceil(std::log2(adj.size()))), par(adj.size()),
	      pow2ends(par.size(), vector<int>(log2dist + 1)), depth(adj.size()) {
		par[root] = depth[root] = -1;
		process(root, root);
 
		for (int n = 0; n < par.size(); n++) { pow2ends[n][0] = par[n]; }
		for (int p = 1; p <= log2dist; p++) {
			for (int n = 0; n < par.size(); n++) {
				int halfway = pow2ends[n][p - 1];
				if (halfway == -1) {
					pow2ends[n][p] = -1;
				} else {
					pow2ends[n][p] = pow2ends[halfway][p - 1];
				}
			}
		}
	}
 
	/** @return el k-ésimo padre del nodo n */
	int kth_parent(int n, int k) {
		if (k > par.size()) { return -1; }
		int at = n;
		for (int pow = 0; pow <= log2dist; pow++) {
			if ((k & (1 << pow)) != 0) {
				at = pow2ends[at][pow];
				if (at == -1) { break; }
			}
		}
		return at;
	}
 
	/** @return el LCA de los nodos n1 y n2 */
	int lca(int n1, int n2) {
		if (depth[n1] < depth[n2]) { return lca(n2, n1); }
		// elevar n1 a la misma altura que n2
		n1 = kth_parent(n1, depth[n1] - depth[n2]);
		if (n1 == n2) {
			return n2;  // en este caso, n2 es un ancestro directo de n1
		}
 
		// subir los nodos mientras no se encuentren
		for (int i = log2dist; i >= 0; i--) {
			if (pow2ends[n1][i] != pow2ends[n2][i]) {
				n1 = pow2ends[n1][i];
				n2 = pow2ends[n2][i];
			}
		}
		// en este punto, el LCA es el padre de cualquiera de los dos nodos
		return pow2ends[n1][0];
	}
};
 
int main() {
	int employee_num;
	int query_num;
	std::cin >> employee_num >> query_num;
	vector<vector<int>> adj(employee_num);
	for (int e = 1; e < employee_num; e++) {
		int boss;
		std::cin >> boss;
		adj[--boss].push_back(e);
		adj[e].push_back(boss);
	}
 
	Tree tree(adj);
	for (int q = 0; q < query_num; q++) {
		int e1, e2;
		std::cin >> e1 >> e2;
		cout << tree.lca(--e1, --e2) + 1 << '\n';
	}
}

Explicación 2

También podemos usar un tour de Euler del árbol para ayudarnos a calcular los LCA.

Sean $\texttt{start}$ y $\texttt{end}$ las tablas de tiempo de entrada y tiempo de salida de los nodos del árbol. Se llenan exactamente igual que en el módulo del tour de Euler.

Lo interesante es que, mientras llenamos $\texttt{start}$ y $\texttt{end}$ , también podemos calcular la tabla de elevación binaria de la misma forma que en la solución anterior. Esto se puede porque en un DFS estamos seguros de haber procesado todos los padres de un nodo antes que el nodo mismo, así que las tablas de cualquier ancestro de un nodo ya estarán llenas cuando lleguemos a ese nodo.

Ahora, para calcular el LCA sin las profundidades de los nodos, podemos usar que el nodo $a$ es ancestro del nodo $b$ si $\texttt{start}[a] \le \texttt{start}[b]$ y $\texttt{end}[b] \le \texttt{end}[a]$ .

En nuestra función de LCA, primero chequeamos si un nodo ya es ancestro del otro. En ese caso, devolvemos el ancestro. Si no lo es, entonces elevamos uno de los nodos hasta que sea ancestro del otro, con un método básicamente igual al algoritmo de elevación binaria anterior. Después de eso, la respuesta es el padre del nodo que elevamos.

Implementación

Complejidad temporal: $\mathcal{O}((N+Q)\log N)$

C++


#include <cmath>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
class Tree {
  private:
	const int root = 0;
 
	const vector<vector<int>> &adj;
	const int log2dist;
	vector<vector<int>> pow2ends;
	vector<int> start, end;
	int timer = 0;
 
	void process(int at, int prev) {
		pow2ends[at][0] = prev;
		for (int p = 1; p <= log2dist; p++) {
			int halfway = pow2ends[at][p - 1];
			if (halfway == -1) {
				pow2ends[at][p] = -1;
			} else {
				pow2ends[at][p] = pow2ends[halfway][p - 1];
			}
		}
 
		start[at] = timer++;
		for (int n : adj[at]) {
			if (n != prev) { process(n, at); }
		}
		end[at] = timer;
	}
 
  public:
	Tree(const vector<vector<int>> &adj)
	    : adj(adj), log2dist(std::ceil(std::log2(adj.size()))),
	      pow2ends(adj.size(), vector<int>(log2dist + 1)), start(adj.size()),
	      end(adj.size()) {
		process(root, -1);
	}
 
	bool is_ancestor(int n1, int n2) {
		return start[n1] <= start[n2] && end[n2] <= end[n1];
	}
 
	int lca(int n1, int n2) {
		if (is_ancestor(n1, n2)) { return n1; }
		if (is_ancestor(n2, n1)) { return n2; }
		for (int i = log2dist; i >= 0; i--) {
			if (pow2ends[n1][i] != -1 && !is_ancestor(pow2ends[n1][i], n2)) {
				n1 = pow2ends[n1][i];
			}
		}
		return pow2ends[n1][0];
	}
};
 
int main() {
	int employee_num;
	int query_num;
	std::cin >> employee_num >> query_num;
	vector<vector<int>> adj(employee_num);
	for (int e = 1; e < employee_num; e++) {
		int boss;
		std::cin >> boss;
		adj[--boss].push_back(e);
		adj[e].push_back(boss);
	}
 
	Tree tree(adj);
	for (int q = 0; q < query_num; q++) {
		int e1, e2;
		std::cin >> e1 >> e2;
		cout << tree.lca(--e1, --e2) + 1 << '\n';
	}
}

Explicación 3

También podemos hallar el LCA de dos nodos con el algoritmo LCA offline de Tarjan.

Aprovechando el recorrido DFS, podemos precomputar las respuestas a las consultas formando subárboles y calculando el padre común con una estructura similar a Union-Find / conjuntos disjuntos.

Implementación

C++


#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 2e5 + 1;
bool vis[MAX];
int lca[MAX], fa[MAX];
vector<array<int, 2>> adj[MAX], qry[MAX];
int find(int u) { return (fa[u] == u) ? u : fa[u] = find(fa[u]); }
void tarjan(int node) {
	vis[node] = true;
	for (auto [nxt, id] : adj[node]) {
		if (vis[nxt]) { continue; }
		tarjan(nxt);
		fa[nxt] = node;
	}
	for (auto &[nxt, id] : qry[node]) {
		if (vis[nxt]) { lca[id] = find(nxt); }
	}
}
int main() {
	int n, m;
	cin >> n >> m;
	iota(fa, fa + n + 1, 0);
	for (int i = 2; i <= n; i++) {
		int a;
		cin >> a;
		adj[i].push_back({a, i});
		adj[a].push_back({i, i});
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		qry[a].push_back({b, i});
		qry[b].push_back({a, i});
	}
	tarjan(1);
	for (int i = 0; i < m; i++) { cout << lca[i] << "\n"; }
}

Recursos
Fuente	Recurso	Notas
cp-algo	LCA with Binary Lifting

Mejoras

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Distance Queries	Fácil	LCA	en el módulo

Explicación

Como tenemos la profundidad de todos los nodos, la distancia entre dos nodos $a$ y $b$ es $\texttt{depth}[a] + \texttt{depth}[b] - 2 \cdot \texttt{depth}[\textrm{lca}(a, b)]$ .

Acá hay algo de intuición por si no queda claro cómo funciona esta fórmula. Para ir del nodo $a$ al $b$ , una forma sería subir a la raíz del árbol y después bajar a $b$ . Eso da una distancia de $\texttt{depth}[a] + \texttt{depth}[b]$ . Sin embargo, observemos que estamos pasando por todos los nodos por encima del LCA dos veces. Por eso hay que restar dos veces la profundidad del LCA, y obtenemos la expresión final.

Implementación

Complejidad temporal: $\mathcal{O}((N+Q)\log N)$

C++


#include <cmath>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
// BeginCodeSnip{LCA Tree}
class Tree {
  private:
	const int root = 0;
 
	const vector<vector<int>> &adj;
	const int log2dist;
	vector<int> par;
	vector<vector<int>> pow2ends;
	vector<int> depth;
 
	void process(int at, int prev) {
		depth[at] = depth[prev] + 1;
		for (int n : adj[at]) {
			if (n != prev) {
				process(n, at);
				par[n] = at;
			}
		}
	}
 
  public:
	Tree(const vector<vector<int>> &adj)
	    : adj(adj), log2dist(std::ceil(std::log2(adj.size()))), par(adj.size()),
	      pow2ends(par.size(), vector<int>(log2dist + 1)), depth(adj.size()) {
		par[root] = depth[root] = -1;
		process(root, root);
 
		for (int n = 0; n < par.size(); n++) { pow2ends[n][0] = par[n]; }
		for (int p = 1; p <= log2dist; p++) {
			for (int n = 0; n < par.size(); n++) {
				int halfway = pow2ends[n][p - 1];
				if (halfway == -1) {
					pow2ends[n][p] = -1;
				} else {
					pow2ends[n][p] = pow2ends[halfway][p - 1];
				}
			}
		}
	}
 
	int kth_parent(int n, int k) {
		if (k > par.size()) { return -1; }
		int at = n;
		for (int pow = 0; pow <= log2dist; pow++) {
			if ((k & (1 << pow)) != 0) {
				at = pow2ends[at][pow];
				if (at == -1) { break; }
			}
		}
		return at;
	}
 
	int lca(int n1, int n2) {
		if (depth[n1] < depth[n2]) { return lca(n2, n1); }
		n1 = kth_parent(n1, depth[n1] - depth[n2]);
		if (n1 == n2) { return n2; }
 
		for (int i = log2dist; i >= 0; i--) {
			if (pow2ends[n1][i] != pow2ends[n2][i]) {
				n1 = pow2ends[n1][i];
				n2 = pow2ends[n2][i];
			}
		}
 
		return pow2ends[n1][0];
	}
	// EndCodeSnip
 
	/** @return la distancia entre los nodos n1 y n2  */
	int distance(int n1, int n2) {
		return depth[n1] + depth[n2] - depth[lca(n1, n2)] * 2;
	}
};
 
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
 
	int node_num;
	int query_num;
	std::cin >> node_num >> query_num;
	vector<vector<int>> adj(node_num);
	for (int e = 0; e < node_num - 1; e++) {
		int a, b;
		std::cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
 
	Tree tree(adj);
	for (int q = 0; q < query_num; q++) {
		int n1, n2;
		std::cin >> n1 >> n2;
		cout << tree.distance(--n1, --n2) << '\n';
	}
}

Problemas

USACO

Fuente	Nombre	Dificultad	Tags	Solución
Platinum	Max Flow	Fácil	LCA	Solución
Platinum	Disruption	Normal	LCA	Solución
Old Gold	Running Away From the Barn	Normal	Small to Large, Binary Jumping, Euler Tour	—
Platinum	Tree Boxes	Difícil	LCA	Solución
Platinum	New Barns	Difícil	Diameter	Solución
Platinum	Gathering	Difícil	LCA	—
Platinum	Exercise Route	Muy difícil	LCA	—

Generales

Fuente	Nombre	Dificultad	Tags	Solución
CF	Sloth Naptime	Fácil	Binary Jumping	Solución
CF	Duff in the Army	Normal	LCA	Solución
Baltic OI	2017 - Railway	Normal		Solución
CF	MST for Each Edge	Normal	LCA	Solución
CF	★ Omsk Metro (hard version)	Normal	LCA	Solución
CSA	Root LCA Queries	Normal	LCA	Solución
CF	Two Paths	Normal	LCA	—
Back to School	Hot & Cold	Normal	LCA	Solución
Google Kickstart	Dependent Events	Difícil	LCA, Binary Jumping, DFS	Solución
CF	Double Tree	Difícil	LCA, Binary Jumping	—
TLX	Functional Constraint	Difícil	LCA	—
TLX	Graph & Destination	Difícil	LCA	—