Escrito por Caique Paiva e Enzo Dantas
Recap:
- Caso não saiba ou não lembre o que é um grafo, veja a aula de introdução a grafos.
Definições:
Uma árvore é um grafo sem ciclos e conexo. Veja um exemplo de uma árvore:
O legal das árvores é que elas tem várias propiedades interessantes. Por exemplo, se uma árvore tem $$n$$ vértices, então ela tem $$n-1$$ arestas. No final do texto tem uma prova mais detalhada, porém o foco dessa aula não é provar esses lemas.
Podemos definir uma árvore por meio de pais e filhos (Também chamados de ancestrais e descendentes). Escolhemos um vértice para ser a raiz, então, os vértices adjacentes a raiz vão ser os filhos da raiz, e os vértices adjacentes a esses filhos vão ser os filhos dos filhos da raiz, e assim vai. Além disso, se subirmos nessa árvore, dizemos que um vértice $$u$$ é pai de $$v$$ se $$v$$ é filho de $$u$$.
Por exemplo, no grafo acima, $$1$$ é a raiz, os filhos de $$1$$ são $$2, 3, 4$$, ou seja, o pai de $$2, 3, 4$$ é o vértice $$1$$, o pai de $$7$$ é o $$3$$, o pai do $$5$$ e do $$6$$ é o $$2$$, e o pai do $$8$$ é o $$6$$.
Além disso, a altura de um vértice é a distância de um vértice para a raiz. Dependendo de por onde você enraiza o grafo,os valores dos pais, dos filhos, e das alturas vão mudar também. Por exemplo, as alturas do grafo acima são:
Uma sub-árvore de um vértice $$v$$ são os filhos de $$v$$, os filhos dos filhos de $$v$$, e assim vai até acabar todos os vértices. Por exemplo, a sub-árvore de $$2$$ são os vértices $$2, 5, 6, 8$$.
Uma folha de uma árvore é um vértice sem filhos. Por exemplo, as folhas da árvore acima são os vértices $$4, 5, 7, 8$$.
Um detalhe importante é que a árvore facilita muitas coisas que normalmente não podem ser feitas em grafos gerais. Um grafo com ciclos, por exemplo, não permitiria uma $$dp$$ tal que a $$dp$$ de um vértice depende diretamente da $$dp$$ dos vértices adjacentes, pois ficaríamos girando em algum ciclo infinitamente*. Como uma árvore não tem ciclos, isso não é um problema, e é comum a ocorrência de problemas em que a $$dp$$ de um vértice depende da dp de seus filhos. Vamos resolver uma questão para deixar a ideia mais clara.
*Talvez contra-intuitivamente, algoritmos de menor caminho são dp’s, mas eles conseguem contornar esse problema utilizando uma ideia gulosa esperta. Caso queira entender melhor, veja a aula de menor caminho.
Problema
Dado uma estrutura de uma empresa, sua tarefa é calcular para cara funcionário o número de subordinados.
Input
A primeira linha tem um inteiro $$n$$: O número de funcionários. Os funcionários estão numerados em $$1, 2, \cdots, n$$ e o funcionario $$1$$ é o diretor geral da empresa.
Depois disso, tem $$n-1$$ inteiros: para cada funcionário $$2, 3, \cdots, n$$ seu chefe direto na compania.
Output
Imprima $$n$$ inteiros: para cara funcionário $$1, 2, \cdots, n$$, o número de subordinados.
Constantes
$$1 \le n \le 2\cdot 10^5$$
Exemplo:
Exemplo:
| Entrada | Saída |
5 1 1 2 3 |
4 1 1 0 0 |
Para submeter o seu código, use esse link.
[spoiler title=’Dica’ style=’purple’ collapse_link=’true’]O problema nos dá a estrutura de uma árvore (N vértices, N-1 arestas, sem ciclos). Com isso, tente pensar em uma dp nessa árvore, com os casos bases sendo os filhos e a transição sendo do pai para os filhos dele.[/spoiler]
[spoiler title=’Solução’ style=’blue’ collapse_link=’false’]
Seja $$dp[v]$$ uma dp que calcula a quantidade de vértices na sub-árvore de $$v$$ (O grafo está enraizado no vértice 1, pois ele não tem chefes). Para uma folha, a quantidade de subordinados que ele tem é 0, então a $$dp[v]$$ (onde $$v$$ é uma folha) é 1. Além disso, a resposta do nosso problema vai ser $$dp[u]-1$$ (Pois $$dp[u]$$ conta também o próprio $$u$$). Então, a transição da $$dp[v]$$ vai ser a seguinte:
$$dp[v] = \sum_{x \text{ filho de }v} (dp[x]) + 1$$
Então, no final basta retornar todas as $$dp$$’s em ordem.
Agora, a parte mais importante desse problema definitivamente é o código, pois isso ensina uma nova forma de fazer uma dfs!
Ao invés de fazer um mark, vamos fazer dfs(int $$v$$, int $$p$$), e $$p$$ vai ser o pai de $$v$$. Então, no for para descer nos filhos, faça um if para ver se $$x == p$$ – se sim, ignore esse vértice e continue o for. Isso ajuda a simplificar o código, o que é sempre bem vindo.
Segue o código para melhor entendimento. Como é o primeiro problema, é recomendado que você leia o código, entenda, feche-o e tente fazer o seu próprio.
[/spoiler]
Problemas Propostos:
Introdutórios:
Journey
Linear LCA
Tree Distances II
Desafios:
Tree Diameter
Tree Matching
[spoiler title=’Prova do lema de árvores’ style=’default’ collapse_link=’true’]
Lema: Se uma árvore tem $$n$$ vértices, então ela tem $$n-1$$ arestas.
Imagine que temos N árvores isoladas. Adicionemos uma nova aresta que conecta duas árvores previamente não conectadas. Por definição, nenhuma das duas árvores tem ciclo, e ao adicionar essa nova aresta, nenhum ciclo é criado (isso só aconteceria caso fosse criada uma aresta entre dois vértices que já estavam conectados). Logo, o novo grafo é uma árvore pois é conexo e sem ciclos. Perceba também que cada operação de juntar duas árvore diminui em exatamente 1 o número de componentes isoladas, então faremos essa operação exatamente N-1 vezes para obter exatamente 1 componente.
Por fim, perceba que um vértice isolado é uma árvore (pois ele é conexo e sem ciclos) e que ele possui k=1 vértices e k-1=0 arestas. Logo, para se construir uma grafo conexo sem ciclos a partir de um conjunto de N vértices isolados, usamos exatamente N-1 arestas.
Caso queira ver mais teoremas matemáticos (e suas provas) sobre árvores e grafos em geral, o noic de matemática tem um material interessante para você!
[/spoiler]