Aula por Arthur Lobo
Conhecimento prévio necessário:
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: