Help with a tree-related problem

Revision en1, by AnotherRound, 2017-01-09 23:41:50

I encountered the following problem (from last years' zhautikov olympiad). You're given a rooted tree, representing a structure of volunteers. There are Q queries. Each query is the following: you are given a node and a number Ai of tasks. If the node(a volunteer) has no subordinates(children in the tree) then he does the tasks. If he has K subordinates, then there are two cases: if K divides Ai, then the Ai tasks are distributed evenly across all the children, e.g each subordinate receives Ai/K tasks. If K doesn't divide Ai, then the tasks are discarded. The question is, given the tree and the Q queries, consisting of which volunteer receives tasks first, and how many tasks he receives, print the number of discarded tasks for each query. Constraints: Number of nodes in the tree and number of queries is <= 100,000, number of tasks for each query is max. 1,000,000. Can anyone give me a solution to this problem? I've been thinking awhile and I feel stuck.

Tags tree, queries on tree


  Rev. Lang. By When Δ Comment
en1 English AnotherRound 2017-01-09 23:41:50 999 Initial revision (published)