Maximize Profit

Hard
0/120
Average time to solve is 40m
profile
Contributed by
0 upvote
Asked in company
Dunzo

Problem statement

You are given a tree having ‘N’ nodes, where each node has some coins ‘C[i]’, attached to it.

You are allowed to collect the coins from any node. Your task is to maximize the sum of chosen coins given that you cannot choose coins from adjacent nodes(i.e., nodes which are directly connected by an edge).

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains one integer ‘N’, denoting the number of nodes in the tree.

The following line contains an array ‘C’ of ‘N’ spaced integers denoting the number of coins attached to each node.

The following line ‘N’ - 1 contains two integers ‘x’ and ‘y’ denoting that there is an edge between node ‘x’ and node ‘y’.
Output Format: 
For each test case, print a single integer denoting the maximum coins you can collect.
Note: 
You don't have to take input or output you just have to complete the function.
Constraints: 
1 <= T <= 5
1 <= N <= 10^5
1 <= C[i] <= 10^9 
1 <= x, y <= N 

Time Limit: 1 sec
Sample Input 1:
2
4
1 2 5 4
1 2
2 3
2 4
3
6 5 4
1 2
1 3
Sample Output 1:
10
9
Explanation for Sample Input 1:
In the first test case, you can take 1st, 3rd and 4th node which will give you a total of 10 coins.
In the second test case, you can take the 2nd and 3rd nodes which will give you a total of 9 coins.
Sample Input 2:
2
3 
9 1 3 
1 2
1 3
3
2 2 2
1 2
2 3
Sample Output 2:
9  
4
Hint

Can we check all possible ways to take the coins and find the maximum possible way?

Approaches (2)
Brute Force

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’
Time Complexity

O(2^N), where ‘N’ is the number of nodes in the tree.


 

For each node, we have two options, either to take it or skip it and we are finding all possible combinations, so total time complexity becomes O(2^N).


 

Space Complexity

O(N), where ‘N’ is the number of nodes in the tree.


 

Storing the nodes in adjacency vector and recursively calling children nodes will lead to a space complexity of O(N)


 

Code Solution
(100% EXP penalty)
Maximize Profit
Full screen
Console