Ancestro común más bajo (LCA) - Binary Lifting (elevación binaria)

Sea $G$ un árbol. Para cada consulta de la forma (u, v) queremos encontrar el ancestro común más bajo de los nodos u y v, es decir, queremos encontrar un nodo w que yace en el camino de u al nodo raíz, que yace en el camino de v al nodo raíz, y si hay varios nodos elegimos el que está más lejos del nodo raíz. En otras palabras, el nodo deseado w es el ancestro más bajo de u y v. En particular, si u es un ancestro de v, entonces u es su ancestro común más bajo.

El algoritmo descrito en este artículo necesitará $O(N \log N)$ para preprocesar el árbol, y luego $O(\log N)$ para cada consulta de LCA.

Algoritmo

Para cada nodo precomputaremos su ancestro inmediatamente encima, su ancestro dos nodos encima, su ancestro cuatro encima, etc. Los guardamos en el arreglo up, es decir, up[i][j] es el 2^j-ésimo ancestro encima del nodo i con i=1...N, j=0...ceil(log(N)). Esta información nos permite saltar de cualquier nodo a cualquier ancestro encima de él en tiempo $O(\log N)$ . Podemos computar este arreglo usando un recorrido DFS del árbol.

Para cada nodo también recordaremos el tiempo de la primera visita a este nodo (es decir, el instante en que el DFS descubre el nodo), y el tiempo en que lo dejamos (es decir, después de visitar todos los hijos y salir de la función DFS). Podemos usar esta información para determinar en tiempo constante si un nodo es ancestro de otro nodo.

Supongamos ahora que recibimos una consulta (u, v). Podemos comprobar de inmediato si uno de los nodos es ancestro del otro. En ese caso ese nodo ya es el LCA. Si u no es ancestro de v, y v no es ancestro de u, subimos por los ancestros de u hasta encontrar el nodo más alto (es decir, el más cercano a la raíz) que no es ancestro de v (es decir, un nodo x tal que x no es ancestro de v, pero up[x][0] sí lo es). Podemos encontrar este nodo x en tiempo $O(\log N)$ usando el arreglo up.

Describiremos este proceso con más detalle. Sea L = ceil(log(N)). Supongamos primero que i = L. Si up[u][i] no es ancestro de v, entonces podemos asignar u = up[u][i] y decrementar i. Si up[u][i] es un ancestro, entonces solo decrementamos i. Claramente, después de hacer esto para todos los i no negativos, el nodo u será el nodo deseado: es decir, u todavía no es ancestro de v, pero up[u][0] sí lo es.

Ahora, obviamente, la respuesta al LCA será up[u][0]: es decir, el nodo más bajo entre los ancestros del nodo u que también es ancestro de v.

Así, responder una consulta de LCA iterará i desde ceil(log(N)) hasta 0 y en cada iteración comprueba si un nodo es ancestro del otro. En consecuencia, cada consulta se puede responder en $O(\log N)$ .

Implementación


int n, l;
vector<vector<int>> adj;
 
int timer;
vector<int> tin, tout;
vector<vector<int>> up;
 
void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];
 
    for (int u : adj[v]) {
        if (u != p)
            dfs(u, v);
    }
 
    tout[v] = ++timer;
}
 
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 = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
 
void preprocess(int root) {
    tin.resize(n);
    tout.resize(n);
    timer = 0;
    l = ceil(log2(n));
    up.assign(n, vector<int>(l + 1));
    dfs(root, root);
}

Ancestro común más bajo (LCA) - Binary Lifting (elevación binaria)

Algoritmo

Implementación

Problemas de práctica