OIA-Wiki

Como mencionamos acá, el ancestro común más bajo (“lowest common ancestor” en inglés, abreviado LCA) de dos nodos es un nodo, que contiene en su subárbol a ambos nodos dados, y que de todos los que cumplen eso, es el más bajo. Esto puede ser interesante por ejemplo para conocer el camino (único) entre dos nodos. El camino será ir subiendo desde uno de ellos, yendo a su padre, al padre de su padre, y así hasta llegar al LCA de los nodos, y desde ahí empezar a bajar a través de todos ancestros del segundo nodo, hasta llegar a él.

La manera más intuitiva de hallar el LCA entre $u$ y $v$, es primero, tener las listas de nodos del camino desde ambos hasta la raíz. Es decir por un lado $\{u, padre(u), padre(padre(u)), \ldots, raiz\}$. Y lo mismo para $v$. Es fácil ver que a partir del LCA, todos los nodos van a coincidir, hasta la raiz. Entonces mirando los sufijos de las lista de atrás hacia adelante, el último que coincide es el LCA.

La idea anterior es inmejorable cuando sólo vamos a querer el LCA entre dos nodos. Qué pasa si queremos el LCA entre muchos nodos. Por ejemplo, si nos dieran una lista de pares de nodos, y tuviéramos que consultar eficientemente el LCA entre cada par de nodos dados?

Para esto, es importante primero haber leído el post sobre sparse tables.

Lo que vamos a hacer es justamente una sparse table. Para cada nodo, nos vamos a guardar información sobre el ancestro a distancia $1$ (su padre), el ancestro a distancia $2$, $4$, $8$, y así siguiendo, hasta que no haya más nodos.

Entonces, ¿cómo hayamos el LCA entre dos nodos?

Primero, al nodo que está más abajo, lo “subimos” a su ancestro que está a la misma altura que el otro nodo. Si este ancestro es el otro nodo, entonces el otro nodo es el LCA y terminamos. Y si inicialmente están a la misma altura, en esta parte no hacemos nada.

Ahora, queremos el LCA de dos nodos que están a la misma altura. Simplemente vamos a ir subiendo, pero no de a uno, sino de a la cantidad más grande que podamos.

Es decir, si puedo subir $8$ nodos por ejemplo desde ambos, y no estoy en el mismo nodo, subo a ambos. Si no, es que el LCA está a a lo sumo $8$ niveles de altura. Si el LCA está a menos de $8$, entonces intentamos subir $4$ a ambos nodos. Si subir $4$ niveles a ambos nodos no me deja a ambos en el mismo lugar, subo. Si no, el LCA está a a lo sumo $4$ niveles. Ahora lo mismo intentando subir $2$ niveles, y por último $1$ nivel.

Qué pasa por ejemplo si al subir $8$ estábamos en el mismo nodo, y el LCA era exactamente ese? Entonces luego vamos a subir $4$, luego $2$, y después $1$, sin llegar al mismo nodo. Entonces el LCA va a ser el padre de esos nodos que están a $7$ de los dos en los que empezamos.

Qué pasa si el LCA está a $6$ niveles? Entonces no vamos a poder subir $8$ porque vamos a estar en el mismo, luego subimos $4$, después no vamos a poder subir $2$ porque llegamos al mismo nodo, luego subimos $1$, y de vuelta el LCA es el padre de los nodos en los que estoy

Aprovechando que $1 + 2 + 4 + \ldots + 2^{n-1} = 2^n - 1$, haciendo este procedimiento, vamos a ir subiendo de a potencias de dos mientras no suba al mismo nodo, y el LCA será el padre de los últimos dos nodos que tenga

Dejo el código para un árbol binario formado en el main, cada nodo tiene dos hijos, la raíz la coloco en el $0$, y voy calculando los padres adyacentes a cada nodo en la función rootTree recursiva. Los hijos de cada nodo $i$ son $2*i+1$ y $2*i+2$, hasta que me paso del $N$ ingresado al principio.

lca.cpp

#include<bits/stdc++.h>
 
using namespace std;
 
#define forn(i,n) for(int i=0; i<(int)(n); i++)
#define pb push_back 
 
 
const int maxn=100005;
const int maxlogn=20;
vector<int> level(maxn, -1);
vector< vector<int> > parent(maxn, vector<int>(maxlogn, -1));
vector< vector<int> > grafo;
 
void rootTree(int toy, int vengo, int nivel){
	level[toy]=nivel;
	parent[toy][0]=vengo;
	forn(i, grafo[toy].size()){
		if(grafo[toy][i]==vengo)continue;
		rootTree(grafo[toy][i], toy, nivel+1);
	}
}
 
int LCA(int u, int v){
	if(level[u]<level[v]){
		int tmp=u;
		u=v;
		v=tmp;
	}
	//cout<<"nodo mas abajo "<<u<<endl;
	int log=0;
	while( (1<<log)<=level[u])log++;
	log--;
	//cout<<"LOG = "<<log<<endl;
	for(int i=log; i>=0; i--){
		if(level[u]-(1<<i) >=level[v]){
			//cout<<"subo de "<<u<<" a ";
			u=parent[u][i];
			//cout<<u<<endl;
		}
	}
	//cout<<"mismo nivel "<<u<<" y "<<v<<endl;
	for(int i=log; i>=0; i--){
		if(parent[u][i]!=-1 && parent[u][i]!=parent[v][i]){
			//cout<<"subo de "<<u;
			u=parent[u][i];
			//cout<<" a "<<u<<" y de "<<v<<" a ";
			v=parent[v][i];
			//cout<<v<<endl;
		}
	}
	int p;
	if(v!=u){
		p=parent[v][0];
	}else{
		p=v;
	}
	return p;
}
 
int main(){
	int N;
	cin>>N;
	forn(i, N){
		vector<int> v;
		if(2*i+1<N)v.pb(2*i+1);
		if(2*i+2<N)v.pb(2*i+2);
		if(i>0)v.pb((i-1)/2);
		grafo.pb(v);
	}
	rootTree(0, -1, 0);
	for(int j=1; (1<<j)<N; j++){
		forn(i, grafo.size()){
			if(parent[i][j-1]!=-1){
				parent[i][j]=parent[parent[i][j-1]][j-1];
			}
		}
	}
	int q;
	cin>>q;
	while(q--){
		int u, v;
		cin>>u>>v;
		cout<<LCA(u, v)<<endl;
	}
}

La complejidad del preprocesamiento, donde usamos una especie de programación dinámica para llenar la tabla $padre[N][logN]$ toma tiempo $\large O(N*log(N))$. Y la complejidad para cada query es el tiempo de primero subir al nodo más bajo, adentro del for que movemos el log, y luego ver si puedo subir ambos, los subo en $O(1)$. Luego la complejidad de cada query es $\large O(log(N))$.

También se puede resolver este problema con un Segment Tree, pero los tiempos son parecidos a los de sparse table, e incluso hay problemas que pueden salir modificando un poco la idea de sparse table pero no con la de segment tree. Pueden leer sobre esta manera en este tutorial.

Queries sobre caminos entre pares de nodos

Queries, distancia entre nodos y k-esimo del camino (difícil)