Блог пользователя stopping_by_woods

Problem on DP on trees (Help needed)
Автор stopping_by_woods, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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
→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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

    → Ответить