Menor Ancestral Comum - Binary Lifting

Deixe $G$ ser uma árvore. Para cada consulta da forma (u, v) queremos encontrar o menor ancestral comum dos nós u e v, ou seja, queremos encontrar um nó w que se encontra no caminho de u para o nó raiz e que se encontra no caminho de v para o nó raiz e, se houver vários nós, escolheremos o que estiver mais distante do nó raiz. Em outras palavras, o nó desejado w é o menor ancestral de u e v. Em particular, se u for um ancestral de v, então u é o menor ancestral comum.

O algoritmo descrito neste artigo precisará de $O(N \log N)$ para pré-processar a árvore e, em seguida $O(\log N)$ para cada consulta de LCA(menor ancestral comum).

Algoritmo

Para cada nó pré-calculamos seu ancestral acima dele, seu ancestral dois nós acima, seu ancestral quatro nós acima, etc. Vamos armazená-los na array up, ou seja, up[i][j] é o 2^j-ésimo ancestral acima do nó i com i=1...N, j=0...ceil(log(N)). Essas informações nos permitem pular de qualquer nó para qualquer ancestral acima dele em tempo $O(\log N)$. Podemos calcular essa array usando uma DFS pela árvore.

Para cada nó, também lembraremos a hora da primeira visita desse nó (ou seja, a hora em que a DFS descobre o nó) e a hora em que o deixamos (ou seja, depois de visitarmos todos os filhos e sair da função da DFS). Podemos usar essas informações para determinar em tempo constante se um nó é um ancestral de outro nó.

Suponha que agora recebemos uma consulta (u, v). Podemos verificar imediatamente se um nó é o ancestral do outro. Nesse caso, este nó já é o LCA. Se u não for o ancestral de v, e v não for o ancestral de u, "escalamos" os ancestrais de u até encontrarmos o nó mais alto (ou seja, o mais próximo da raiz), que não é um ancestral de v (ou seja, um nó x, de modo que x não é um ancestral de v, mas up[x][0] é). Podemos encontrar esse nó x em $O(\log N)$ usando a array up.

Vamos descrever esse processo com mais detalhes. Seja L = ceil(log(N)). Suponha primeiro que i = L. Se up[u][i] não é um ancestral de v, então podemos definir u = up[u][i] e decrementar i. Se up[u][i] for um ancestral, então apenas decrementamos i. Depois de fazer isso para todos os não-negativos i, o nó u será o nó desejado - ou seja, u ainda não é um ancestral de v, mas up[u][0] será.

Agora, obviamente, a resposta para o LCA será up[u][0] - ou seja, o menor nó entre os ancestrais do nó u, que também é um ancestral de v.

Portanto, responder a uma consulta de LCA irá iterar i de ceil(log(N)) até 0 e irá verificar em cada iteração se um nó é o ancestral do outro. Consequentemente, cada consulta poderá ser respondida em $O(\log N)$.

Implementação

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