Árbol de reconstrucción de Kruskal

Tutorial

Supongamos que queremos soportar consultas estáticas de camino sobre un árbol de tamaño $N$ para la arista mínima entre dos vértices. Quienes ya tengan nivel avanzado pueden pensar en técnicas como binary lifting, HLD, o incluso LCT para soportar operaciones en complejidad logarítmica. Un árbol de reconstrucción de Kruskal (Kruskal Reconstruction Tree, KRT) puede responder tales consultas en $\mathcal{O}(1)$ con construcción $\mathcal{O}(N \log N)$.

Podemos construir un KRT de la siguiente forma:

• Empezamos con $N$ componentes, cada una representando a cada nodo
• Procesamos cada arista en orden ordenado. Para una arista que conecta $(u,v)$, creamos un nodo auxiliar $f$ que es el padre de los nodos más altos en las componentes de $u$ y $v$. Ahora, $f$ es el nuevo nodo más alto en la componente fusionada.

Observar que mantener las relaciones de las componentes se puede hacer en complejidad logarítmica amortizada usando compresión de caminos de forma similar a un DSU.

Terminamos con un árbol binario de tamaño $2N -1$. Podemos soportar consultas devolviendo el peso de la arista del nodo correspondiente a $\texttt{lca}(u, v)$.

Para una demostración informal de correctitud, considerar lo siguiente:

Considerar el KRT justo antes de agregar el nodo correspondiente a $\texttt{lca}(u, v)$. Por definición de LCA, $u$ y $v$ no están conectados, lo que implica que la arista de peso mínimo no puede tener peso menor que $\texttt{lca}(u, v)$. Además, como todas las aristas agregadas después de la correspondiente a $\texttt{lca}(u, v)$ tienen peso mayor, nuestra respuesta es efectivamente la arista correspondiente a $\texttt{lca}(u, v)$.

Así, usando métodos de LCA en $\mathcal{O}(1)$, podemos responder nuestras consultas con la complejidad mencionada.

Ejemplo - Qpwoeirut and Vertices

Para resolver esta tarea, podemos asignar pesos a las aristas según su índice en el orden de entrada. Luego, podemos construir el árbol de Kruskal, procesando solo aristas entre nodos que aún no están conectados (de forma similar al homónimo del árbol de Kruskal, el algoritmo de Kruskal).

A partir de aquí, necesitamos una forma rápida de consultar el $\text{LCA}$ de un rango de nodos. Una forma de hacerlo es mantener el orden DFS de los nodos, y tomar el $\text{LCA}$ de los nodos con el recorrido más temprano y más tardío dentro del rango. Esto se puede hacer con cualquier estructura de datos de consulta de rango, como una tabla dispersa o un árbol de segmentos.

Implementación

Una complejidad temporal óptima para este problema sería $\mathcal{O}(N+M+Q)$, usando métodos de LCA y RMQ en $\mathcal{O}(1)/\mathcal{O}(N)$. Sin embargo, presentamos una solución $\mathcal{O}((N+Q)\log N + M)$ por simplicidad.

#include <bits/stdc++.h>
using namespace std;
 
constexpr int MAX_N = 4e5 + 5;
constexpr int LG = 20;
 
int n, m, q, va[MAX_N], f[MAX_N], nx;
int trace(int v) { return f[v] == v ? v : f[v] = trace(f[v]); }
 
/** Implements LCA with binary lifting */
namespace LCA {
int lift[MAX_N][LG], ch[MAX_N][2], t, tin[MAX_N], tout[MAX_N], tour[2 * MAX_N];
 
bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
 
int lca(int u, int v) {
	if (is_ancestor(u, v)) { return u; }
	if (is_ancestor(v, u)) { return v; }
 
	for (int i = LG - 1; i >= 0; --i) {
		if (!is_ancestor(lift[u][i], v)) { u = lift[u][i]; }
	}
 
	return lift[u][0];
}
 
void dfs(int v) {
	if (v == -1) { return; }
	tour[t] = v;
	tin[v] = t;
 
	for (int i = 1; i < LG; i++) { lift[v][i] = lift[lift[v][i - 1]][i - 1]; }
 
	dfs(ch[v][0]);
	dfs(ch[v][1]);
	tout[v] = t++;
}
}  // namespace LCA
 
/** Point Update / Range Min/Max Segment Tree */
namespace SGT {
int sg_min[1 << LG + 1], sg_max[1 << LG + 1];
 
void point_set(int i, int v) {
	sg_min[i + (1 << LG)] = sg_max[i + (1 << LG)] = v;
	for (int j = (i + (1 << LG)) / 2; j; j /= 2) {
		sg_min[j] = min(sg_min[2 * j], sg_min[2 * j + 1]),
		sg_max[j] = max(sg_max[2 * j], sg_max[2 * j + 1]);
	}
}
 
/** @return edge (LCA of nodes w/ lowest and highest traversal time in [l, r]) */
int query(int l, int r) {
	int lift = MAX_N, rt = -1;
	for (l += 1 << LG, r += 1 << LG; l < r; l >>= 1, r >>= 1) {
		if (l & 1) { lift = min(lift, sg_min[l]), rt = max(rt, sg_max[l++]); }
		if (r & 1) { lift = min(lift, sg_min[--r]), rt = max(rt, sg_max[r]); }
	}
	return va[LCA::lca(LCA::tour[lift], LCA::tour[rt])];
}
}  // namespace SGT
 
void solve() {
	cin >> n >> m >> q;
 
	iota(f, f + 2 * n, 0);
	nx = n;
	memset(LCA::ch, -1, sizeof(LCA::ch));
 
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		// assign u and v to the top of their component
		u = trace(--u), v = trace(--v);
 
		// if the edge is within one component, no further work is needed
		// otherwise, create a new node that is the parent of both components
 
		if (u == v) { continue; }
		va[nx] = i, LCA::ch[nx][0] = u, LCA::ch[nx][1] = v;
		f[u] = f[v] = LCA::lift[u][0] = LCA::lift[v][0] = nx++;
	}
 
	LCA::lift[2 * n - 2][0] = 2 * n - 2;
	LCA::dfs(2 * n - 2);
 
	// update segment tree for range min/max of dfs-order traversal times
	for (int i = 0; i < 2 * n - 1; i++) { SGT::point_set(i, LCA::tin[i]); }
 
	while (q--) {
		int l, r;
		cin >> l >> r;
		if (l == r) {
			cout << "0 ";
		} else {
			cout << SGT::query(l - 1, r) + 1 << " ";
		}
	}
 
	cout << "\n";
}
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) { solve(); }
}

Problemas