Lowest common ancestor
Neste artigo vamos focar-nos num dos conceitos mais importantes de árvores. Agora que já sabem o que é uma rooted tree, o que corresponde a atribuir uma raiz a uma árvore (caso tenham dúvidas sobre isto, consultem o artigo sobre propriedades básicas de árvores e lê também algum do material extra), vamos considerar para este artigo que sempre que falamos em árvore, falamos numa árvore com raiz.
Considerem dois quaisquer nós $a$ e $b$ de uma árvore. O seu lowest common ancestor é o nó de maior profundidade (mais afastado da raiz) que está presente no caminho de $a$ para a raiz e no caminho de $b$ para a raiz. Este conceito parece um pouco aleatório, mas se pensarem bem, ele é muito importante. Seja $p$ o lowest common ancestor de $a$ e $b$. Podemos decompor o caminho entre $a$ e $b$ como: um caminho entre $a$ e $p$ e um caminho entre $p$ e $b$. Isto significa que se pre-calcularmos certos valores para os caminhos entre um nó e a raiz, podemos compor o resultado usando o lowest common ancestor de maneira eficiente.
Vamos então ler um pouco sobre como calcular e alguns exemplos de como usar a propriedade referida.
Artigo: Perguntas numa árvore
Ler o capítulo 18 do livro Competitive Programmer’s Handbook. Ler ainda a secção 16.3, referida neste capítulo.
Como já devem ter visto na leitura anterior, uma propriedade muito interessante deste problema é que ele é equivalente ao problema de range minimum query. Se não conheces este problema nem as suas soluções, lê o artigo do loop sobre uma possível estrutura de dados usada para resolver o problema chamada árvore de segmentos.
Se quiserem consolidar esta ideia e ver algum código de exemplo, vejam o artigo seguinte:
*Artigo: Lowest common ancestor
Um artigo curto do e-maxx sobre lowest common ancestor.
Se quiserem uma referência mais completa sobre diferentes possíveis soluções, vejam o artigo seguinte:
*Artigo: Lowest common ancestor
Um artigo do HackerRank sobre várias formas de resolver o problema do lowest common ancestor.
Aplicações
Como não poderia faltar, têm aqui dois problemas para aplicar o que aprenderam. O primeiro é um pouco mais direto, mas o segundo obriga a pensar de uma forma muito engraçada sobre distâncias em árvores.
Problema 1: Kth Ancestor
Problema do HackerRank, kth-ancestor, E - Kth Ancestor
*Problema 2: A and B and Lecture Rooms
Problema do CodeForces, Ronda 294, div. 2, E - A and B and Lecture Rooms
Nota: se lerem alguns editoriais das soluções poderão ver mencionada a expressão binary lifting, isto corresponde ao método referido no capítulo 18.1 do livro do primeiro artigo.