There is 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 A(i).
The following operation(s) can be performed any number of times (including zero):
1.choose any node which still exists in the tree and remove the whole sub- tree of this node including itself.
2.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.
How can we calculate 'k' value here?(means no. of time node is deleted to give optimum profit)
Example:-
3(number of nodes,N) ,
5(X)
1 -5 -10 (Values of corresponding nodes)
(edge(s) from 'x'->'y')
1 2
2 3
Output: -4
We remove the sub-tree of node : 2'.
Now,value of our tree is: 1.
Finals answer:- 1-(x)*k,
(k=1); as we have performed the operation of removing the sub-tree only '1' time
: 1-(5)*1= -4.
NOTE:it's not given that tree should be binary it can be a general tree too.
There's a straightforward recursive algorithm for this. The most profitable pruning you can perform on a tree is either to perform the most profitable pruning on all of its direct subtrees, or to just prune away the whole tree. This can be translated directly to code.
Assuming the tree has been processed into a data structure where every node has a value attribute representing the node's value and a children attribute storing a list of the node's child nodes, the following Python function would compute the max profit:
def max_profit(node):
return max(
-X,
node.value + sum(map(max_profit, node.children)))
with the two options in the max call representing the choice to either prune the whole tree away at the root, or to keep the root and process the subtrees.