learner_321's blog

how to solve this problem ?
By learner_321, history, 7 years ago, In English

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)

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it -10 Vote: I do not like it

What is the constraint on the # of nodes?

→ Reply
»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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]))

→ Reply
»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Interesting tutorial here:(probably includes your problem, see problem 1)

http://mirror.codeforces.com/blog/entry/20935

→ Reply