Given a binary tree,where each node has value given x, (x>=0).
you need to find maximum sum of nodes's x value ,but you can not select two nodes in the answer such that one node is parent (only immediate),and other is child.
like if 1 is root , and its left child is 2 and right child is 3 ,then you can not include 1 and 2, or 1 and 3 in the answer,but you can include 2-3.
find maximum possible sum...
Number of nodes<= (1e6)
What is the constraint on the # of nodes?
Seems like you can use dynamic programming here. Let dp1[i] be the answer on subtree of vertex i assuming you use vertex number i in the resulting set. Also dp2[i] be the answer on subtree of vertex i assuming you don't use vertex i. Then, to calculate dp1[i] and dp2[i] you calculate dp1[c] and dp2[c] for each child c of i. Then dp1[i] = sum(dp2[c]) + w[i], dp2[i] = sum(max(dp1[c], dp2[c]))
Interesting tutorial here:(probably includes your problem, see problem 1)
http://codeforces.me/blog/entry/20935