How to find the maximum sum of nodes in a tree

2
votes

I am given two arrays, one defines the relationship of nodes and other gives the values of nodes.

arr1={0,1,1,1,3,3,4}
arr2={22,100,3,3,4,5,9}

arr1 defines the relationship, i.e. root node is 1st element and parent of node 2,3 and 4th is node 1 and parent of node 5th and 6th is root 3rd and parent of node 7th is node 4.

arr2 gives the value of nodes, node 1 have a value of 22 and node 2 has got a value of 100.

I have to find the maximum sum of nodes such that no two included nodes have a parent or a grand parent relationship.

sample input:

a[i]=[0,1,1,1,3,3,6,6]
b[i]=[1,2,3,4,5,100,7,8]

output: 111

I am new to DS and ALGO and not able to even think of the solution. Help is needed thanks. Any type of help will do.

1
calgorithmdata-structurestreedynamic-programming
Are you aware of the concept of traversing a tree? – Yunnosch
Can you simply print all the values in your tree? – Yunnosch
Great grand parent relationship (or more distant) would be OK? – Yunnosch

1 Answers

2
votes

You can solve it using Dynamic Programming. Consider an array dp[] which stores the answer for each of the vertex and its subtree.

Now state of DP would be,

dp[currentVertex] = max(sum of all children's dp[] ,
                        b[currentVertex] + sum of all vertices' dp[] whose 
                        greatGrandParent is currentVertex])

You need to build DP table using bottom-up approach. So start from the leaves.

Answer would be dp[root] after all the calculation.