Romok007's blog

By Romok007, history, 22 months ago, In English,

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

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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