I just had this question during an interview, I think I almost got it but not quite. Any insight into a solution would be great:

​

You are given a tree (not necessarily a binary tree) where each node has a value between 0 and infinity and 0 or more children. Find the maximum sum of the values of the nodes given the constraints that if a node is selected to be part of the sum none of its children can be selected and its parent cannot be selected.

​

For example the solution for the following tree should be 7 (select the node with value 3 and all the leaf nodes)

​

			1
			|
			3
		   / \
		  1   1
		 |\    |\
		1 1    1 1

​

The solution I came up with was a recursive solution that returns the value of using the root node and not using the root :

 
def soln(tree) -> max_sum_including_root, max_sum_excluding_root:
        // base case
        if tree.children.length == 0:
                return tree.val, 0
 
       sub_using_children, sub_not_using_children = 0, 0
       for child in tree.children:
                including_child, not_including_child = soln(child)
                 sub_using_children = sub_using_children + including_child
                 sub_not_using_children = sub_not_using_children + 
                                      not_including_child
 
       return sub_not_using_children + tree.val, sub_using_children
 
// final output
print(max(soln(tree)))

I this solution would work on the example above but I'm missing something (there might be some cases I'm overlooking). Please help me with this problem.