Considere um problema clássico: Luogu P3379, que envolve encontrar o Ancestral Comum Mais Próximo (LCA) em uma árvore.

O que é LCA

LCA, ou Ancestral Comum Mais Próximo, refere-se ao nó mais profundo que é ancestral comum de dois nós dados. Por exemplo, em uma árvore com raiz no nó 0, se definimos LCA(x,y) como o ancestral comum mais próximo de x e y, então LCA(5,6)=2; LCA(4,3)=1; LCA(5,3)=0.

Uma abordagem ingênua seria mover x e y para a mesma profundidade e, em seguida, subir simultaneamente até que se encontrem, mas isso pode ser ineficiente. Em seguida, exploramos dois algoritmos otimizados: Tarjan e elevação binária para LCA.

Algoritmo de Tarjan

O algoritmo de Tarjan é offline e processa todas as consultas de LCA em uma única travessia, o que o torna eficiente. Ele utiliza busca em profundidade (DFS) e estrutura de dados união-busca.

Passos do algoritmo:

1. Inicie a DFS a partir da raiz da árvore. Se o nó atual tiver filhos não visitados, continue a DFS recursivamente.
2. Quando um nó não tem filhos ou todos os filhos foram processados, una o nó atual ao seu pai na estrutura união-busca.
3. Para cada consulta relacionada ao nó atual, se o outro nó já foi processado (retornou da DFS), o LCA é o representante desse nó na união-busca.

A chave é que durante a DFS, ao retornar de um nó, o algoritmo verifica consultas e usa a união-busca para encontrar o ancestral comum.

Simulação

Para ilustrar, considere a mesma árvore com consultas LCA(5,6) e LCA(5,4). A DFS começa na raiz 0, vai para 2, depois 5 (sem filhos). Une 2 e 5. Consultas para 5: 6 e 4 ainda não processados, então ignora. Retorna a 2, vai para 6 (sem filhos), une 2 e 6. Consultas para 6: 5 já processado, então LCA(5,6)=encontrar(6)=2. Continua o processo para outras partes da árvore.

Implementação

Para armazenar a árvore, use uma lista de adjacência bidirecional. As consultas podem ser armazenadas em listas por nó, com índices para manter a ordem de saída. Abaixo, um exemplo de código em C++ para o algoritmo de Tarjan, com variáveis renomeadas e estrutura modificada:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_NOS = 500000;
vector<int> filhos[MAX_NOS];
vector<int> consultas[MAX_NOS];
vector<int> indices_consulta[MAX_NOS];
int pai[MAX_NOS];
int visitado[MAX_NOS]; // 0: não visitado, 1: em processamento, 2: concluído
int respostas[MAX_NOS];

int encontrar(int x) {
    if (pai[x] != x) pai[x] = encontrar(pai[x]);
    return pai[x];
}

void executarTarjan(int no) {
    visitado[no] = 1;
    for (int i = 0; i < filhos[no].size(); i++) {
        int filho = filhos[no][i];
        if (!visitado[filho]) {
            executarTarjan(filho);
            pai[filho] = no;
        }
    }
    for (int i = 0; i < consultas[no].size(); i++) {
        int outro = consultas[no][i];
        if (visitado[outro] == 2) {
            int raiz = encontrar(outro);
            respostas[indices_consulta[no][i]] = raiz;
        }
    }
    visitado[no] = 2;
}

int main() {
    int n, m, raiz;
    cin >> n >> m >> raiz;
    for (int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        filhos[u].push_back(v);
        filhos[v].push_back(u);
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        consultas[a].push_back(b);
        consultas[b].push_back(a);
        indices_consulta[a].push_back(i);
        indices_consulta[b].push_back(i);
    }
    for (int i = 1; i <= n; i++) pai[i] = i;
    executarTarjan(raiz);
    for (int i = 0; i < m; i++) cout << respostas[i] << endl;
    return 0;
}

LCA por Elevação Binária

A elevação binária melhora o método ingênuo ao permitir saltos em potências de dois. Primeiro, pré-calcule a profundidade de cada nó e uma tabela para pular até 2^i ancestrais. A relação de recorrência é: se f[m][i] é o ancestral de m a 2^i passos, então f[m][i] = f[f[m][i-1]][i-1], com f[m][0] sendo o pai direto.

Para encontrar LCA(a,b): primeiro, equalize as profundidades usando saltos binários. Em seguida, suba ambos os nós simultaneamente, garantindo que não ultrapassem o LCA. Finalmente, o pai do nó resultante é o LCA.

Abaixo, um código em C++ para LCA por elevação binária, com variáveis renomeadas e lógica reestruturada:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_NOS = 500000;
const int MAX_LOG = 20;
vector<int> arestas[MAX_NOS];
int ancestral[MAX_NOS][MAX_LOG];
int profundidade[MAX_NOS];

void preprocessar(int no, int pai_atual) {
    ancestral[no][0] = pai_atual;
    profundidade[no] = profundidade[pai_atual] + 1;
    for (int i = 1; (1 << i) <= profundidade[no]; i++) {
        ancestral[no][i] = ancestral[ancestral[no][i-1]][i-1];
    }
    for (int i = 0; i < arestas[no].size(); i++) {
        int vizinho = arestas[no][i];
        if (vizinho != pai_atual) preprocessar(vizinho, no);
    }
}

int lca(int u, int v) {
    if (profundidade[u] < profundidade[v]) swap(u, v);
    for (int i = MAX_LOG-1; i >= 0; i--) {
        if (profundidade[u] - (1 << i) >= profundidade[v]) {
            u = ancestral[u][i];
        }
    }
    if (u == v) return u;
    for (int i = MAX_LOG-1; i >= 0; i--) {
        if (ancestral[u][i] != ancestral[v][i]) {
            u = ancestral[u][i];
            v = ancestral[v][i];
        }
    }
    return ancestral[u][0];
}

int main() {
    int n, m, raiz;
    cin >> n >> m >> raiz;
    for (int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        arestas[u].push_back(v);
        arestas[v].push_back(u);
    }
    preprocessar(raiz, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }
    return 0;
}

Esses algoritmos permitem resolver o LCA de forma eficiente, com Tarjan sendo ideal para consultas offline e elevação binária para consultas online.