Maximize Profit

Now let’s take a simple tree.

Now if we take coins at node 1 then for sure we can not take coins present at nodes 2 and 3, but if we skip node 1 then, we have two options for each of the other two nodes .i.e we can either take or skip them. 

To generalise this, we can say that if we take the parent node, we need to skip all its direct children nodes and if we skip the parent node, we can either take its children node or skip it. 

Let F(x, b) be a recursive function that takes a node and a boolean value and depending upon the boolean value it returns the maximum number of coins we can take from the subtree of that node. 

1. When the boolean value is 1, we are going to take the coins present in the current node and skip all its children. Let ‘y1’, ‘y2’, .. ‘yn’ be the children nodes of x. So final expression becomes:

F(x, 1) = ‘C[x]’ + F(y1, 0) + F(y2, 0) + F(y3, 0) + … F(yn, 0).

1. When the boolean value is 0, we are going to find the maximum number of coins from the subtree if we skip the present node. Since we are skipping the present node we have an option to either take or skip its chid nodes. So final expression becomes:

F(x, 0) = max(F(y1, 0), F(y1, 1) + max(F(y2, 0), F(y2,1) + ..  max(F(yn,0), F(yn,1).

Since we need to find the maximum number of coins we can take from the whole tree so the final answer is going to be the maximum of F(root,0) and F(root,1).

Algorithm: 

• Create an adjacency vector ‘V’ of size ‘N’ to store the edges.
• Iterate through all the edges
  • Decrement ‘x’ and ‘y’ by 1 to make it 0 based index
  • Insert ‘y’ at ‘V[x]’ and ‘x’ at ‘V[y]’.
• Create a function ‘F’ which takes three parameters, ‘node’, ‘parentNode’ and a boolean variable ‘b’.
  • Initialize ‘sum’ to 0
  • Iterate through all the children of ‘node’
    • If current children is equal to ‘parentNode’ then continue
    • Let ‘x’ be the current children
    • If ‘b’ is 1, add F(‘x’,’node’,0) to ‘sum’
    • If ‘b’ is 0, add max(F(‘x’, ‘node’,0), F(‘x’, ‘node’, 1) to ‘sum’.
  • If ‘b’ is 1, add ‘C[node]’ to ‘sum’
  • Return sum.
• Initialize ‘ans’ to maximum of F(0,0,0) and F(0,0,1)
• Return ‘ans’

Let’s look at how the brute force approach will work on the following tree.

After calling F(1,1) we get

After calling F(1,0) we get,

Notice that we are recalculating many states which were earlier visited such as (3,0). We can avoid such states by memorising them and directly returning the values when we reach an already visited state. 

Algorithm: 

• Create an adjacency vector ‘V’ of size ‘N’ to store the edges.
• Initialize a 2d array ‘dp’ of size ‘N’ * 2 with -1
• Iterate through all the edges
  • Decrement ‘x’ and ‘y’ by 1 to make it 0 based index
  • Insert ‘y’ at ‘V[x]’ and ‘x’ at ‘V[y]’.
• Create a function ‘F’ which takes three parameters, ‘node’, ‘parentNode’ and a boolean variable ‘b’.
  • If ‘dp[node][b]’ is not -1, return ‘dp[node][b]’
  • Initialize ‘sum’ to 0
  • Iterate through all the children of ‘node’
    • If current children is equal to ‘parentNode’ then continue
    • Let ‘x’ be the current children
    • If ‘b’ is 1, add F(‘x’,’node’,0) to ‘sum’
    • If ‘b’ is 0, add max(F(‘x’, ‘node’,0), F(‘x’, ‘node’, 1) to ‘sum’.
  • If ‘b’ is 1, add ‘C[node]’ to ‘sum’
  • Update ‘dp[node][b]’ to ‘sum’
  • Return sum.
• Initialize ‘ans’ to maximum of F(0,0,0) and F(0,0,1)
• Return ‘ans’