Introdução a Árvores

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.

Dica

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.

[collapse]

Solução

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.

Problemas Propostos:

Introdutórios:
Journey
Linear LCA
Tree Distances II

Desafios:
Tree Diameter
Tree Matching

Prova do lema de árvores

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ê!

[collapse]