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