Subtree Removal - Editorial with code [Codechef April 2019 Long Challenge]

Problem:

We are given a rooted tree with N nodes where Node 1 is the root. We are asked to perform the following operation any number of times(could also be 0): Select a node and remove the whole subtree(including the node itself).
Let's define Profit as the sum of all existing nodes in the tree. After performing the given operation K times subtract X*K from Profit. Find the maximum possible profit.

Solution:
Let's focus on understanding the last part of the problem. We define Profit as the sum of all the existing nodes in the tree. After we have performed the subtree removal operation K times, we are asked to subtract X*K from the profit. But instead of subtracting X*K at last we could subtract X from the Profit after each subtree removal operation. Since the operation is performed K times, it would mean the same thing as subtracting X*K at last would have.

Keeping this in mind, let's try to find out which subtrees should be removed such that the profit could be maximized.

We traverse through all the tree nodes and at every node we have 2 options:
1)Cut down the whole subtree(including the node). If we decide to cut down the subtree, a cost of X will be incurred.i.e we have to subtract X from the Profit.
                       OR
2)Keep the node. If we decide to keep the node. the sum of all the nodes in the subtree(including the node itself) will be added to the Profit.

So, max(option 1,option 2) is the optimal solution at every node.

Code:
We use a simple recursive function to evaluate the max profit. Note that the given input is an undirected tree so we have to use a visited vector. My code with detailed explanation can be found in this link:

https://github.com/nishant-boro/i_love_algos/blob/master/cc_april2019_subtree-removal

Time complexity: O(n) to visit all the nodes.