Ancestro común más bajo (LCA) - $O(\sqrt{N})$

c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,-10,-9.5,-14 c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54 c44.2,-33.3,65.8,-50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10 s173,378,173,378c0.7,0,35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429 c69,-144,104.5,-217.7,106.5,-221 l0 -0 c5.3,-9.3,12,-14,20,-14 H400000v40H845.2724 s-225.272,467,-225.272,467s-235,486,-235,486c-2.7,4.7,-9,7,-19,7 c-6,0,-10,-1,-12,-3s-194,-422,-194,-422s-65,47,-65,47z M834 80h400000v40h-400000z”/>) y $O(\log N)$ con preprocesamiento $O(N)$

Se da un árbol $G$ . Se dan consultas de la forma $(v_1, v_2)$ ; para cada consulta hay que encontrar el ancestro común más bajo (lowest common ancestor, también llamado least common ancestor), es decir, un vértice $v$ que yace en el camino de la raíz a $v_1$ y en el camino de la raíz a $v_2$ , y el vértice debe ser el más bajo. En otras palabras, el vértice deseado $v$ es el ancestro más bajo de $v_1$ y $v_2$ . Es evidente que su ancestro común más bajo yace en un camino más corto entre $v_1$ y $v_2$ . Además, si $v_1$ es ancestro de $v_2$ , $v_1$ es su ancestro común más bajo.

La idea del algoritmo

Antes de responder las consultas, hay que preprocesar el árbol. Hacemos un recorrido DFS empezando en la raíz y construimos una lista $\text{euler}$ que guarda el orden de los vértices que visitamos (un vértice se agrega a la lista cuando lo visitamos por primera vez, y después de que regresan los recorridos DFS a sus hijos). Esto también se llama un tour de Euler del árbol. Es claro que el tamaño de esta lista será $O(N)$ . También hay que construir un arreglo $\text{first}[0..N-1]$ que guarda, para cada vértice $i$ , su primera aparición en $\text{euler}$ . Es decir, la primera posición en $\text{euler}$ tal que $\text{euler}[\text{first}[i]] = i$ . Además, usando el DFS podemos hallar la altura de cada nodo (distancia desde la raíz hasta él) y guardarla en el arreglo $\text{height}[0..N-1]$ .

Entonces, ¿cómo podemos responder consultas usando el tour de Euler y los dos arreglos adicionales? Supongamos que la consulta es un par $v_1$ y $v_2$ . Consideremos los vértices que visitamos en el tour de Euler entre la primera visita de $v_1$ y la primera visita de $v_2$ . Es fácil ver que el $\text{LCA}(v_1, v_2)$ es el vértice con la menor altura en este camino. Ya observamos que el LCA tiene que formar parte del camino más corto entre $v_1$ y $v_2$ . Claramente también tiene que ser el vértice con la menor altura. Y en el tour de Euler esencialmente usamos el camino más corto, salvo que además visitamos todos los subárboles que encontramos en el camino. Pero todos los vértices de esos subárboles están más abajo en el árbol que el LCA y por lo tanto tienen una altura mayor. Así, el $\text{LCA}(v_1, v_2)$ se puede determinar de forma única buscando el vértice con la menor altura en el tour de Euler entre $\text{first}(v_1)$ y $\text{first}(v_2)$ .

Ilustremos esta idea. Consideremos el siguiente grafo y el tour de Euler con las alturas correspondientes:

$\begin{array}{lccccccccccccc} Vertices: & 1 & 2 & 5 & 2 & 6 & 2 & 1 & 3 & 1 & 4 & 7 & 4 & 1 \\ Heights: & 1 & 2 & 3 & 2 & 3 & 2 & 1 & 2 & 1 & 2 & 3 & 2 & 1 \end{array}$

En el tour que empieza en el vértice $6$ y termina en $4$ visitamos los vértices $[6, 2, 1, 3, 1, 4]$ . Entre esos vértices, el vértice $1$ tiene la menor altura; por lo tanto $\text{LCA(6, 4) = 1}$ .

Recapitulando: para responder una consulta solo hay que encontrar el vértice con menor altura en el arreglo $\text{euler}$ en el rango de $\text{first}[v_1]$ a $\text{first}[v_2]$ . Así, el problema de LCA se reduce al problema RMQ (encontrar el mínimo en un rango).

Usando descomposición por raíz cuadrada, es posible obtener una solución que responde cada consulta en $O(\sqrt{N})$ con preprocesamiento en tiempo $O(N)$ .

Usando un Árbol de Segmentos se puede responder cada consulta en $O(\log N)$ con preprocesamiento en tiempo $O(N)$ .

Como casi nunca habrá actualizaciones de los valores almacenados, una Tabla Dispersa (Sparse Table) podría ser una mejor elección, permitiendo responder consultas en $O(1)$ con tiempo de construcción $O(N\log N)$ .

Implementación

En la siguiente implementación del algoritmo de LCA se usa un Árbol de Segmentos.


struct LCA {
    vector<int> height, euler, first, segtree;
    vector<bool> visited;
    int n;

    LCA(vector<vector<int>> &adj, int root = 0) {
        n = adj.size();
        height.resize(n);
        first.resize(n);
        euler.reserve(n * 2);
        visited.assign(n, false);
        dfs(adj, root);
        int m = euler.size();
        segtree.resize(m * 4);
        build(1, 0, m - 1);
    }

    void dfs(vector<vector<int>> &adj, int node, int h = 0) {
        visited[node] = true;
        height[node] = h;
        first[node] = euler.size();
        euler.push_back(node);
        for (auto to : adj[node]) {
            if (!visited[to]) {
                dfs(adj, to, h + 1);
                euler.push_back(node);
            }
        }
    }

    void build(int node, int b, int e) {
        if (b == e) {
            segtree[node] = euler[b];
        } else {
            int mid = (b + e) / 2;
            build(node << 1, b, mid);
            build(node << 1 | 1, mid + 1, e);
            int l = segtree[node << 1], r = segtree[node << 1 | 1];
            segtree[node] = (height[l] < height[r]) ? l : r;
        }
    }

    int query(int node, int b, int e, int L, int R) {
        if (b > R || e < L)
            return -1;
        if (b >= L && e <= R)
            return segtree[node];
        int mid = (b + e) >> 1;

        int left = query(node << 1, b, mid, L, R);
        int right = query(node << 1 | 1, mid + 1, e, L, R);
        if (left == -1) return right;
        if (right == -1) return left;
        return height[left] < height[right] ? left : right;
    }

    int lca(int u, int v) {
        int left = first[u], right = first[v];
        if (left > right)
            swap(left, right);
        return query(1, 0, euler.size() - 1, left, right);
    }
};

Ancestro común más bajo (LCA) - O(N)O(\sqrt{N})O(N<path d=“M95,702

La idea del algoritmo

Implementación

Problemas de práctica

Ancestro común más bajo (LCA) - $O(\sqrt{N})$