**1**results.

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.