Village Fair 2

Limits: 5s, 512 MB

There are N houses in a village far away from here. They are numbered from 1 to N. For this problem lets assume, the houses each can accommodate infinite amount of people. From each house there is a directed path to exactly one other house. One of the houses is a grand house. There is a fair going on currently in the grand house. From this house there is no exit, and everybody can enjoy the festival here. It is guaranteed that there is exactly one simple way from each house to the grand house. The house numbered 1 is the grand house. Initially there is a little kid in each of the houses of the village. Each kid has some non-negative amount of joy(they are all pretty excited about the fair). Every kid from their house starts their journey to the grand house. When they go from a house to some other house, their joy changes by some amount. This change depends on the path. If at any point of time some kid’s joy value becomes negative he returns to home. Note that this kid is not counted in later part. Now, for each houses, you have to count the number of distinct non-negative joy values that will come to this house at some point of time. Note that if two or more persons with the same joy value will be counted only once. See the sample explanation for details.


This is a companion discussion topic for the original entry at https://toph.co/p/village-fair-2