Aula - Introdução à DP em árvore

Aula por Arthur Lobo

Conhecimento prévio necessário:

Introdução à Programação Dinâmica

Assim como podemos usar DP (Dynamic Programming) para resolver problemas em sequências lineares (como o problema do troco), também podemos usá-las para resolver problemas em árvores.

Nos problemas de Programação Dinâmica em árvore, geralmente vamos enraizar a árvore em algum vértice arbitrário (comummente escolhemos o 1) e a DP vai guardar informações sobre cada subárvore do grafo. Ou seja, $dp_u$ vai guardar alguma informação sobre a subárvore de $u$ , mas normalmente vão ter mais estados do que apenas qual a subárvore. Mas considerando que existe apenas um estado (a raiz da subárvore), vai ser nesse formato:

Caso base: Toda DP precisa ter um caso base. No caso de DP em árvore esse caso vão ser as folhas (vértices que não tem filhos). Sempre conseguimos calcular o valor de $dp_u$ em $O(1)$ se $u$ for uma folha.
Transição: Para calcular o valor de $dp_u$ , vamos primeiro ter que calcular o valor da $dp$ de todos os filhos de $u$ , e então calcular $dp_u$ baseado nesses valores. A exata transição sempre vai depender do problema.
Resposta: Depois de calcular todas as $dp$ , a resposta do problema geralmente vai ser $dp_{raiz}$ (ou 1, se raiz for 1). Mas assim como a transição, isso vai depender do problema.

A ideia é que $dp_u$ vai guardar alguma informação se estivermos olhando para uma árvore é que apenas a subárvore de $u$ e, com a informação das subárvores dos filhos de $u$ , podemos calcular $dp_u$ , fazendo isso das folhas até chegar na raiz.

Obs: Quando se referimos à subárvore de $u$ em uma árvore enraizada, estamos nos referindo à todo vértice $v$ que passa por $u$ no caminho até a raiz (incluindo o próprio $u$ ).

Motivação Inicial

Vamos imaginar o seguinte problema:

Dado uma árvore de $N$ vértices e $N-1$ arestas, vértice $i$ ( $1 \le i \le N$ ) tem $C_i$ moedas. Você pode escolher um conjunto de vértices nessa árvore e pegar as moedas dos vértices nesse conjunto, mas tem um detalhe: não podem existir dois vértices adjacentes no conjunto. Diga qual é a maior soma de moedas de um conjunto válido.

Formalmente, qual o maior valor da soma $C_{v_1} +C_{v_2} + ... + C_{v_k}$ tal que $v_1,v_2,..,v_k$ é um subconjunto de vértices da árvore e não existem dois vértices adjacentes (ou seja, que são diretamente ligados por uma arestas) presentes nesse conjunto. Vale ressaltar que $k$ não é um valor fixo, apenas o tamanho do conjunto.

Clique aqui para conferir o enunciado inteiro

Solução

A ideia nesse problema é fazermos uma DP em árvore com 2 estados: Um vai ser falando qual subárvore estamos vendo e o outro diz se a raiz está no conjunto escolhido ou não. Então a $dp$ será:

$dp_{u,0}$ = maior soma olhando apenas para a subárvore de $u$ e $u$ não é um dos vértices escolhidos. Ou seja, esse é o maior valor da soma $C_{v_1} +C_{v_2} + ... + C_{v_k}$ , tal que $v_1,v_2,..,v_k$ é um subconjunto de vértices da subárvore de e $u$ não está nesse subconjunto.
$dp_{u,1}$ = maior soma olhando apenas para a subárvore de $u$ e $u$ é um dos vértices escolhidos. Ou seja, esse é o maior valor da soma $C_{v_1} +C_{v_2} + ... + C_{v_k}$ , tal que $v_1,v_2,..,v_k$ é um subconjunto de vértices da subárvore de e $u$ está nesse subconjunto.

Pare por alguns instantes e tente imaginar como seriam os casos base, as transições e a resposta dessa DP. Tentou? Então vamos lá:

Primeiro vamos imaginar para $dp_{u,0}$ :

Caso base: Como falado a cima, os casos bases da nossa DP serão as folhas. Se $u$ é uma folha e não escolhemos ele para o subconjunto, então $dp_{u,0} = 0$ .
Transição: Primeiro temos que calcular o valor das DP todos os filhos de $u$ . Depois de fazermos isso, vamos olhar para cada filho $f$ de $u$ . Já que o $u$ não foi escolhido para estar no subconjunto, o $f$ pode estar ou não nele, então podemos pegar o melhor valor entre $dp_{f,0}$ e $dp_{f,1}$ . Ou seja, se o $u$ não foi escolhido para estar no subconjunto, então todas as subárvores dos filhos dele serão livres para ter ou não a raiz escolhida. Formalmente, $dp_{u,0} = \sum_{f \in filhos \hspace{0.1cm} de \hspace{0.1cm} u} max(dp_{f,0},dp_{f,1})$ .

Agora para $dp_{u,1}$ :

Caso base: Se $u$ é uma folha e escolhemos ele para o subconjunto, então $dp_{u,1} = C_u$ .
Transição: Depois de calcularmos as DP dos filhos, vamos olhar para cada filho $f$ de $u$ . Já que o $u$ foi escolhido para estar no subconjunto, o $f$ não pode estar nele (pois $u$ é adjacente à $f$ ), então somos obrigados a pegar $dp_{f,0}$ . Ou seja, se o $u$ foi escolhido para estar no subconjunto, então todas as subárvores dos filhos dele serão obrigadas a não escolherem a raiz. Além disso, já que escolhemos a raiz, temos que adicionar $C_u$ . Formalmente, $dp_{u,1} = C_u + \sum_{f \in filhos \hspace{0.1cm} de \hspace{0.1cm} u} dp_{f,0}$ .

Lembrando que temos que calcular ambas as DP ao mesmo tempo, então na $dfs(u)$ vamos calcular $dp{u,0}$ e $dp{u,1}$ . Agora a resposta será simplesmente o maior valor entre colocar a raiz (provavelmente o 1) e não colocá-lo. Ou seja $resposta = max(dp{raiz,0},dp{raiz,1}$ .

Código: