Unable to understand the editorial and the approach

#1

I am not able to solve this question, kindly guide on how to approach this question.

#2

@Vishal_234 first start traversing tree from root(1 with initial distance as 0), now if you encounter any node such that dist>value[node], then this node must be removed, also to remove this node you have to actually remove the whole sub-tree! so just count number of nodes within this sub-tree. Take care that while travelling pass distance as max(0,current_distance+value[u,v]) as distance might become -ve as well!
This will ensure that you don’t have to consider every pair of (u,v) hence overall complexity is O(n)

#3

But if i am checking only for the distance from the root, then there may be case where the distance from the root to a particular node U could be less than the value(U) but between this pair(root,U), there may be a vertex V such that distance between (V,U) is greater than value(U).How is this condition checked in this approach ?

#4

this takes care of what you are saying!

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.