Comentário OBOI 2023 Segunda Fase – Problema “Bonsai”

Comentário por Henrique Vianna

Conhecimento prévio necessário:

• DP em Árvore
• Problema da Mochila (Knapsack)
• Euler Tour

Perceba que o enunciado se resume ao seguinte: Dada uma árvore $T$ em que os vértices possuem valores $v[i]$ (que podem inclusive ser negativos), maximize $\sum_{u \in T}v[u]$ após a remoção de até $K$ vértices, juntos às suas respectivas subárvores. Na resolução desse exercício, analisaremos cada uma das parciais, antes de chegar à solução final.

Parcial 1: A árvore é uma linha, ou seja, $u[i] = i, v[i] = i + 1$  $\forall 1 \leq i \leq N - 1$.

Nessa parcial, podemos imaginar a a árvore como um vetor, em que as operações que podemos fazer é remover um sufixo seu. Perceba entretanto, que o valor de $K$ é irrelevante: sempre existe uma solução ótima em que exatamente um sufixo é removido, podendo esse ser nulo. Por consequência, sempre manteremos um prefixo desse vetor, ou seja, a resposta é simplesmente a maior soma de prefixo de $T$.

Parcial 2: $1 \leq N \leq 10^3$ e $1 \leq K \leq 100$

Para resolver essa parcial, faremos uso de uma dp, sendo que:

$dp[u][j]$ é o minimo que consigo remover com exatamente $j$ operações entre os vértices da subárvore de $u$.

A recorrência dessa dp é relativamente simples. Faremos uso de uma segunda dp, $dp2$, para nos auxiliar nessa recorrência:

$dp2[i][j]$ é o minimo que consigo remover em $j$ operações considerando os $i$ primeiros filhos de $u$.

A recorrência de $dp2[i][j]$ é bastante similar à DP clássica da Knapsack: deve-se brutar, para o filho atual, quantas operações serão feitas dentro de sua subárvore. Chamaremos esse numero de $c$. Sendo assim:

$dp2[i][j] = min(dp2[i - 1][j], dp2[i - 1][j - c] + dp[v][c])$, tal que $1 \leq c \leq j$

Ao final, para termos os valores de $dp[u][j]$ de fato, basta fazermos:

$dp[u][j] = dp2[f][j]$, sendo $f$ o numero de filhos de $u$.

A resposta é simplesmente $\sum_{i= 1}^{N}v[i] - min(dp[1][j])$, com $1 \leq j \leq K$.

Parcial 2: Sem restrições adicionais.

A $dp$ acima, apesar de ser suficiente para a parcial 2, não é rápida o suficiente para obter-se $100$ pontos, haja vista sua complexidade de $\mathcal{O}(N*K^2)$. Precisamos, portanto, otimizá-la. Uma maneira inteligente de fazer isso é “linearizar” a árvore, fazendo uma $dp$ similar a essa em seu Euler Tour. Para tanto, basta calcularmos o $tin$ e $tout$ de cada um dos vértices numa $dfs$ inicial. Calcularemos a $dp$ nos vértices ordenados por $tin$. Define-se:

$dp[i][j]$ é o minimo que consigo remover com exatamente $j$ operações entre os  $i$ últimos vértices do Euler Tour.

Vale notar que estamos calculando a nossa $dp$ no sufixo, ou seja, passando do ultimo vértice do Euler Tour ao primeiro. A recorrência, portanto, é dada por:

$dp[i][j] = min(dp[i + 1][j],dp[tout[tour[i]+1]][j-1]+sub[tour[i])$, sendo que $sub[u]$ guarda a soma dos $v[i]$ na subárvore de $u$.

A resposta é calculada da mesma forma que na parcial $2$. Sendo assim, conseguimos resolver o problema em $\mathcal{O}(N*K)$.

Para melhor compreensão, confira o código aqui.