Rectangle 27 0

Lets say dp[u][select] stores the answer: maximum sub sequence sum with no two nodes having edge such that we consider only the sub-tree rooted at node u ( such that u is selected or not ). Now you can write a recursive program where state of each recursion is (u,select) where u means root of the sub graph being considered and select means whether or not we select node u. So we get the following pseudo code

/* Initialize dp[][] to be -1 for all values (u,select) */
     /* Select is 0 or 1 for false/true respectively        */

     int func(int node , int select )
     {
         if(dp[node][select] != -1)return dp[node][select];
         int ans = 0,i;

         // assuming value of node is same as node number
         if(select)ans=node;

         //edges[i] stores children of node i
         for(i=0;i<edges[node].size();i++)
         {
             if(select)ans=ans+func(edges[node][i],1-select);
             else ans=ans+max(func(edges[node][i],0),func(edges[node][i],1));
         }
         dp[node][select] = ans;
         return ans;
     }

     // from main call, root is root of tree and answer is
     // your final answer
     answer = max(func(root,0),func(root,1));

We have used memoization in addition to recursion to reduce time complexity.Its O(V+E) in both space and time. You can see here a working version of the code Code. Click on the fork on top right corner to run on test case 4 1 1 2 1 5 2 3 2 4 It gives output 12 as expected. The input format is specified in comments in the code along with other clarifications. Its in C++ but there is not significant changes if you want it in python once you understand the code. Do post in comments if you have any doubts regarding the code.

I have specified the input format and given a link you can run on your testcases also

yes it is the test case, I don't get your doubt.

Sorry, I didn't realize that the first two arguments are the number of edges and the root node and thought that they were parent child nodes as well.

Algorithm to find the maximum non-adjacent sum in n-ary tree - Stack O...

algorithm tree dynamic-programming maximize