Comentário por Henrique Vianna
Conhecimento prévio necessário:
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.