[USACO 2010 Hol G]Rocks and Trees

My country's bigger than most

And if asked I boast

'Cause I'm really proud

So I shout it loud

Though our numbers are few

We will welcome you

Although we don't have history

Gold medal winning teams

Heroes or prisoners

World famous volcanoes

Still what we've got's glorious

'Cause we've got

Rocks and trees

And trees and rocks

And rocks and trees

And trees and rocks

And rocks and trees

And trees and rocks

And rocks and trees

And trees and rocks

And water

-The Arrogant Worms, on Canada

After moving across the 49th parallel to Canada, the land of rocks and trees, Farmer John's cows invented a game to spend their leisure time on the pasture; naturally, it involved the rocks and trees! Cowboy Ted likes this game very much, but so poor is his luck that he always loses to other cows. This time, he is going to seek your help.
The game's rules are simple. It is played with a tree that has both N (2 <= N <= 10,000) nodes conveniently numbered 1..N and also N-1 branches. Node 1 is the root of this tree; except for node 1, node i has parent $P_i$ (1 <= $P_i$ < i). Initially, Each node contains some rocks (except the root node, which has no rocks). In particular, non-root node i has exactly $R_i$ (1 <= $R_i$ <= 1,000) rocks at the beginning of the game.
Two players alternate turns to play this game in turn, with Ted going first. In each turn, the current player can choose a non-root node i and move at most L (1 <= L <= 1,000) rocks from this node one branch closer to the root (i.e., move these rocks to the parent node). He must move at least one rock, and, of course, he cannot exceed the current number of rocks on this node. The game ends when a player can't make a legal move (i.e., when all the rocks are on node 1); that player loses.
Ted needs your help. He has given you the initial configuration of the game, and he will then make T (1 <= T <= 10,000) changes to the configuration one by one. Please help him determine, after each step, if he can win the game beginning from this configuration, assuming both he and his opponent use the best possible strategy.
Ted's changes are specified as two integers $A_j$ (1 < $A_j$ <= N) and $B_j$ (1 <= $B_j$ <= 1,000), meaning that Ted will change the number of rocks on node $A_j$ to $B_j$ (this is a 'set' not a 'subtract' or 'add'), and will then ask you whether he can win. Changes accumulate; node $A_j$ 's rocks stay at $B_j$ until another change for $A_j$ appears.

Consider this example with three nodes numbered as shown and the shape shown in Board 0. Initially, there are 5 rocks on node 2 and 3 rocks on node 3; see Board 1.

For the first change, Ted removes 2 rocks from node 2 (thus leaving 3); see Board 2. For the second change, Ted removes 2 rocks from node 3 (thus leaving 1). Note that node 2 still has 3 rocks; see Board 3.

1 - - -

/ \ / \ / \ / \

2 3 5 3 3 3 3 1

Board 0 Board 1 Board 2 Board 3

Your program should determine in each case who wins.

For about 30% of the test cases, N <= 10, and T <= 100, and no tree node will have more than 5 rocks on it after any of Ted's changes.

详情