Menor Ancestral Comum - $O(\sqrt{N})$ e $O(\log N)$ com $O(N)$ de pré-processamento

Dada uma árvore $G$ e consultas da forma $(v_1, v_2)$, para cada consulta/query você precisa encontrar o menor ancestral comum ou seja, um vértice $v$ que se encontra no caminho da raiz para $v_1$ e no caminho da raiz para $v_2$, e o vértice deve ser o mais baixo. Em outras palavras, o vértice desejado $v$ é o ancestral mais baixo de $v_1$ e $v_2$. O menor ancestral comum deles está no caminho mais curto de $v_1$ e $v_2$. Além disso, se $v_1$ é o ancestral de $v_2$, $v_1$ é o menor ancestral comum.

A ideia do algoritmo

Antes de responder às queries, precisamos pré-processar a árvore. Fazemos uma travessia com a DFS a partir da raiz e criamos uma lista $\text{euler}$ que armazena a ordem dos vértices que visitamos (um vértice é adicionado à lista quando o visitamos pela primeira vez e após o retorno da travessia da DFS para os vértices filhos). Isso também é chamado de tour de Euler pela árvore. É claro que o tamanho desta lista será $O(N)$. Também precisamos criar uma array $\text{first}[0..N-1]$ que armazene para cada vértice $i$ sua primeira ocorrência em $\text{euler}$. Ou seja, a primeira posição em $\text{euler}$ na qual $\text{euler}[\text{first}[i]] = i$. Além disso, usando a DFS, podemos encontrar a altura de cada nó (distância da raiz até ele) e armazená-lo na array $\text{height}[0..N-1]$.

Então, como podemos responder as consultas usando o tour de Euler e as duas arrays? Suponha que a consulta seja um par de $v_1$ e $v_2$. Considere os vértices que visitamos no tour de Euler entre a primeira visita de $v_1$ e a primeira visita de $v_2$. O $\text{LCA}(v_1, v_2)$ é o vértice com a menor altura nesse caminho. Já vimos que o LCA deve fazer parte do caminho mais curto entre $v_1$ e $v_2$. Claramente, também deve ser o vértice com a menor altura. E no tour de Euler, usamos essencialmente o caminho mais curto, exceto que também visitamos todas as subárvores que encontramos no caminho. Mas todos os vértices nessas subárvores são mais baixos na árvore que o LCA e, portanto, têm uma altura maior. Portanto, o $\text{LCA}(v_1, v_2)$ pode ser determinado unicamente encontrando o vértice com a menor altura no tour de Euler entre $\text{first}(v_1)$ e $\text{first}(v_2)$.

Vamos ilustrar essa ideia. Considere o grafo a seguir e o tour de Euler com as alturas correspondentes:

LCA_Euler_Tour
$$\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{Vertices:} & 1 & 2 & 5 & 2 & 6 & 2 & 1 & 3 & 1 & 4 & 7 & 4 & 1 \\ \hline \text{Alturas:} & 1 & 2 & 3 & 2 & 3 & 2 & 1 & 2 & 1 & 2 & 3 & 2 & 1 \\ \hline \end{array}$$

O tour começando no vértice $6$ e terminando no $4$, visitamos os vértices $[6, 2, 1, 3, 1, 4]$. Entre esses vértices, o vértice $1$ tem a menor altura, portanto $\text{LCA(6, 4) = 1}$.

Para recapitular: para responder a uma consulta, precisamos apenas encontrar o vértice com a menor altura na array $\text{euler}$ no intervalo de $\text{first}[v_1]$ para $\text{first}[v_2]$. Assim, o problema do LCA é reduzido ao problema do RMQ (encontrando o mínimo em um intervalo).

Usando Sqrt-Decomposition, é possível obter uma solução respondendo a cada consulta em $O(\sqrt{N})$ com pré-processamento em tempo $O(N)$.

Usando uma Árvore Segmentária você pode responder a cada consulta em $O(\log N)$ com pré-processamento em tempo $O(N)$.

Implementação

Uma Árvore Segmentária é usada na implementação do algoritmo do LCA abaixo.

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);
    }
};

Problemas