Skip to Content
CTRL K

Company Queries II

Explicación

Este problema nos pide hallar el ancestro común más bajo (LCA) de dos nodos en un árbol. Aunque se puede resolver con binary lifting / elevación binaria, usaremos descomposición Heavy-Light (HLD) para practicar la técnica.

Preprocesamiento de HLD:

  • Calcular tamaños de subárboles para identificar los hijos heavy
  • Descomponer el árbol en caminos heavy
  • Asignar cada nodo a una cadena de camino heavy y guardar el nodo tope

La idea clave es que podemos saltar de forma eficiente entre cadenas de caminos heavy al recorrer desde el nodo aa hasta el nodo bb. Para hallar el LCA de dos nodos:

  1. Mover repetidamente el nodo cuya cadena de camino heavy es más profunda hacia su cadena padre
  2. Cuando ambos nodos están en la misma cadena de camino heavy, el nodo con menor profundidad es el LCA

Cualquier camino pasa por a lo sumo log⁡N\log N aristas light y por lo tanto necesita saltar por un máximo de log⁡N\log N caminos heavy.

Implementación

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

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
const int N = 2e5 + 5;
 
int n, q;
vector<int> adj[N];
 
int sz[N], p[N], dep[N];
int tp[N];  // tope de la cadena de camino heavy
 
void dfs_sz(int cur, int par) {
	sz[cur] = 1;
	p[cur] = par;
	for (int chi : adj[cur]) {
		if (chi == par) continue;
		dep[chi] = dep[cur] + 1;
		dfs_sz(chi, cur);
		sz[cur] += sz[chi];
	}
}
 
void dfs_hld(int cur, int par, int top) {
	tp[cur] = top;
 
	// hallar el hijo heavy (hijo con el subárbol más grande)
	int h_chi = -1, h_sz = -1;
	for (int chi : adj[cur]) {
		if (chi == par) continue;
		if (sz[chi] > h_sz) {
			h_sz = sz[chi];
			h_chi = chi;
		}
	}
 
	if (h_chi == -1) return;  // nodo hoja
 
	// extender el camino heavy hacia el hijo heavy
	dfs_hld(h_chi, cur, top);
 
	// empezar caminos heavy nuevos para los hijos light
	for (int chi : adj[cur]) {
		if (chi == par || chi == h_chi) continue;
		dfs_hld(chi, cur, chi);
	}
}
 
int lca(int x, int y) {
	// subir en el árbol hasta que ambos nodos estén en el mismo camino heavy
	while (tp[x] != tp[y]) {
		// mover el nodo cuyo tope de camino heavy es más profundo
		if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
		x = p[tp[x]];
	}
	// ambos en el mismo camino heavy, devolver el más superficial
	return dep[x] < dep[y] ? x : y;
}
 
int main() {
	cin >> n >> q;
 
	for (int i = 2; i <= n; i++) {
		int boss;
		cin >> boss;
		adj[boss].push_back(i);
		adj[i].push_back(boss);
	}
 
	dep[1] = 0;
	dfs_sz(1, 0);
	dfs_hld(1, 0, 1);
 
	while (q--) {
		int a, b;
		cin >> a >> b;
		cout << lca(a, b) << "\n";
	}
}
Fundamentos