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

Автор Romok007, история, 7 лет назад, По-английски

Can someone please help me with the solution of this problem? (https://www.hackerrank.com/contests/h42-prelims-1/challenges/will-and-good-trees)

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

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

Make array P, where P[u] is sum of elements on path 1->u. Now problem is to check if there are u, v such that P[u] — P[v] = k. To solve it use dfs and store cnt structure.

When you are visiting u, cnt[x] will be the count of such v that P[v] = x and v belongs 1->u. If there is such u that cnt[P[u]-k] isn't zero, tree is good. All you need is to modify cnt to make it valid.

There is some code, i didn't check it: link