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