Decomposição heavy-light

Agora que já passámos pelo problema do lowest common ancestor (se não sabes o que isto é, lê o artigo do loop sobre o assunto), vamos passar a uma técnica um pouco mais complexa. Nota que esta técnica é bastante mais avançada e por isso requer que já tenham alguma experiência em concursos (muitos problemas resolvidos) e dominem bem os temas relativos a árvores. Mas não se assustem, se trabalharem, não é assim tão difícil!

Ora, imaginem que temos um problema parecido com o mencionado no artigo de lowest common ancestor, em que nos dão uma árvore pesada (pesos nas arestas) e $Q$ pares de nós e perguntam-nos para cada par de nós $a$ e $b$, qual é a distância entre $a$ e $b$. Já vimos que podemos para cada para $a$ e $b$, encontrar o seu lowest common ancestor (ou apenas lca) $p$ e decompor o caminho em dois caminhos: um de $a$ para $p$ e outro de $p$ para $b$. Se pre-calcularmos a distância de cada nó à raiz, é fácil calcular o comprimento destes dois caminhos. Ora, vamos complicar, e se entre os pares de nós que temos de verificar a distância, os pesos das arestas forem mudando, ou seja, a certa altura dizem-nos que agora a aresta $e_1$ tem peso 5 depois que a $e_2$ tem peso 1, e por ai fora. Aqui o problema complica-se bastante, vamos ter de fazer algo mais do que um simples pre-cálculo.

Uma solução possível passa por decompormos a árvore em "cadeias" de nós. Para isto marcamos cada aresta como heavy ou light, dependendo do tamanho da subárvore que parte dela. Porquê isto? Vamos ler com mais detalhe no próximo artigo.

Esta decomposição é muito versátil, visto que em cada cadeia podemos ter qualquer estrutura de dados a fazer qualquer tipo de operação! Isto significa que podemos modelar inúmeros tipos de problemas aqui. Se tiverem passado por alguns dos problemas das provas de seleção das ONI dos anos anteriores, podem-se ter deparado com o problema C de 2015, Semáforos. Se pensarem bem, este problema pode ser resolvido com esta técnica, sendo que a operação a fazer é apenas verificar se todos os semáforos estão verdes (que pode ser feito ou com uma árvore de segmentos ou até com uma árvore binária de pesquisa).

Se quiserem mais uma leitura sobre o tópico, confiram o próximo artigo

Notem ainda que este conceito de olhar para elementos heavy e elementos light de uma estrutura pode ser aplicada noutros contextos. Pensem num grafo qualquer por exemplo. Se o grafo tem $E$ arestas e $V$ vértices, podemos classificar os nós do grafo como heavy ou light da seguinte forma:

• Nós heavy: nós que têm $\sqrt{E}$ ou mais vizinhos;
• Nós light: nós que têm menos de $\sqrt{E}$ vizinhos;

Agora, sabemos que existem no máximo $\sqrt{E}$ nós heavy, caso contrário o grafo teria de ter mais de $E$ arestas. Logo, podemos pre-calcular alguma coisa para estes nós e usar o facto que os nós light têm menos de $\sqrt{E}$ vizinhos. Por exemplo, consegues ver como utilizar isto para contar quantos triângulos existem num grafo? Ou seja, dado um grafo $G$ quantos subgrafos de 3 nós de $G$ existem que são triângulos (o grafo completo com 3 nós)?

Aplicações

Vamos aplicar isto num problema. Este primeiro problema é uma aplicação direta do método, por isso não devem ter dificuldades em chegar à solução, mas cuidado com a implementação! Como já devem ter visto, não será muito simples, por isso sejam organizados.

Se ainda estiverem com vontade, têm aqui um outro problema para aplicar o conceito de decomposição heavy light, mas neste caso numa outra situação, de solução menos óbvia.

* Decomposição centroide

Antes de terminarmos, vamos ver um último método, semelhante ao anterior, mas com aplicações diferentes. Na decomposição heavy light pensamos em termos de elementos "pesados" e "leves" de uma estrutura, agora vamos pensar em termos de elementos centrais. Vejam um artigo muito bom sobre o assunto:

Se estiveram atentos aos problemas das finais das ONI passadas, devem-se recordar de um problema em particular, o problema C de 2017, Torre defeituosa. Neste problema interativo pediam-nos para encontrar uma torre defeituosa no mínimo número de adivinhas possível. Se leram a solução deste problema, então devem ter reparado que menciona centroides. De facto, o tipo de pesquisa que fazemos neste problema exatamente o mesmo que fazemos numa decomposição centroide! Por isso, agora o problema deve ter ficado muito mais simplificado nas vossas cabeças.

Aplicações

Se ainda quiserem mesmo resolver algum problema, têm aqui um problema que sem conhecer esta técnica parece ser completamente impossível. Felizmente, vocês já conhecem, por isso não vos deve dar muito trabalho a chegarem a uma solução.