Problem 3: Running Away From the Barn [Richard Peng, 2012]

It's milking time at Farmer John's farm, but the cows have all run away! Farmer John needs to round them all up, and needs your help in the search.

FJ's farm is a series of N (1 <= N <= 200,000) pastures numbered 1...N connected by N - 1 bidirectional paths. The barn is located at pasture 1, and it is possible to reach any pasture from the barn.

FJ's cows were in their pastures this morning, but who knows where they ran to by now. FJ does know that the cows only run away from the barn, and they are too lazy to run a distance of more than L. For every pasture, FJ wants to know how many different pastures cows starting in that pasture could have ended up in.

Note: 64-bit integers (int64 in Pascal, long long in C/C++ and long in Java) are needed to store the distance values.

#3801 upload 1 done 1 how_to_reg 1

Running Away From the Barn timer 1s memory 128MB

#3801

Running Away From the Barn 1s 128MB