The key here is to recognize that the bacteria spread in a wave from parent to child. To compute the number of bacteria at node N at time T, you need to start at the root node at time T-D where D is the depth of node N. Then run through the rules for each second as you descend the graph from the root to node N, keeping track of the total bacteria as you go.
To do this you need to store the graph. Within each node, store the number of bacteria that were added by a query (NOT the number added by the parent's bacteria spreading), and the time (second) when the bacteria appeared there. Since Chef can add bacteria to a cell several times, you'll need a collection of these.
You should also store a pointer or index to the node's parent.
When you get a + query, you add that bacteria count & timestamp to the node.
When you get a ? query, you start at cell v and recursively go up the tree, counting the depth until you get to the root. Suppose you discover that v is at depth 5. Then start at time T-5 and see if any bacteria was added to the root at that time. If so then add that to your count.
Now, as you unwind the recursion, you descend the tree back to node v. At the next second (T-4), "count" bacteria migrated to the root's child on the path. Check if Chef added any bacteria to that child at time T-4. If so, you'll need to add that number to your total count.
And then you go to the next child and do the same calculation for time T-3
and down and down to the node that was queried.
Now somethings I hate about CodeChef problems.
|Let's denote the number of sons of vertex v by sv|
Let's denote Chef's sexist attitude by a raised middle finger.
|For each non-leaf vertex v...|
And what about the leaf vertices? Chef says that the parent's bacteria spreads down to the leaf, but then what happens to it? Does it die in the next second? Does it live forever? Does it fly away on a unicorn and come back next summer? The example seems to indicate that bacteria stop at the leaf and fester there forever.