Need help with a codechef problem

Правка en1, от apjcoder123, 2022-03-06 15:07:09

Hello everyone. Recently, I came across this problem on Codechef: https://www.codechef.com/LP3TO401/problems/SUBREM

I came across this kind of problem for the first time. It will be really helpful if could get to know the type of this problem. I guess this is a problem in DP on trees. It would be really helpful if I get to know the name of this topic and some beginner to medium level practice problems on this topic.

Problem Statement:

You are given a rooted tree with N nodes (numbered 1 through N); node 1 is the root. Each node has a value; let's denote the value of node i by Ai.

You may perform the following operation any number of times (including zero): choose any node which still exists in the tree and remove the whole subtree of this node including itself.

Let's define the profit as the sum of values of all nodes which currently exist in the tree minus X⋅k, where k denotes the number of times this operation was performed. Find the maximum possible profit.

----------------------------------------------------------------------------------------------------------------------------- Thanking you all in advance.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский apjcoder123 2022-03-06 15:08:36 127
en1 Английский apjcoder123 2022-03-06 15:07:09 1306 Initial revision (published)