stopping_by_woods's blog

Problem on DP on trees (Help needed)
By stopping_by_woods, history, 4 years ago, In English

Problem Link

Can someone help how to do this problem. The editorial is a bit unclear to me. I am finding it difficult to make transitions between the dp states. Thanks in advance!

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys, please help. I know knapsack dp, which I think will be used in this, but I don't have much experience in dp on trees problems.

Problem statement in short
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    In my solution i have used these two concepts for transition:-

    1.when you have root R with value C, X ways to get value A in a subtree rooted at left son of R, and Y ways to get value B in subtree rooted at right son of R, it gives you X*Y ways to get value A+B+C in subtree rooted at R(from editorial). Above example is just for two childs but you can extend this for >2 number of childs as well.

    2.While solving "subset sum problem with linear space" we traverse from backward in dp to avoid multiple counting of same value.You can use same concept here.

    link of "subset sum problem with linear space" video editorial :- https://www.youtube.com/watch?v=-httet0UVUU&t=1s link of my solution with comment :- https://ideone.com/Fplthb

    → Reply