Baltic Olympiad in Informatics: 2013 Day 1, Problem 1
We have a "ball machine" that can be visualized as a rooted tree. The nodes of the tree are numbered
from to
. Each node is either empty or contains one ball. Initially, all nodes are empty. While
running, the machine can perform operations of two different types:
- Add
balls to the ball machine: Balls are put one by one into the root node. As long as a ball has an empty node directly beneath it, it will roll down. If there are multiple empty child nodes, the ball will choose the one which has the node with the smallest number in its subtree. So if the ball rolls down multiple levels, it makes a choice at each level. For example: If we add two balls to the machine in the picture below, they will go to nodes
and
: The first ball rolls from node
to node
because node
is empty and it contains node
in its subtree (which consists of nodes
and
); it further rolls from node
to node
. The second ball rolls from node
to node
as well and stops there.
- Remove a ball from a specified node: This node becomes empty and balls from above (if there
are any) roll down. Whenever a parent of an empty node contains a ball, this ball will roll down.
If we remove balls from nodes
,
and
(in this order) from the machine in the picture below, nodes
,
and
will become empty.
![](https://static.dmoj.ca/media/martor/4e44752a-878a-4896-aedc-da975946f396.png)
Constraints
Input Specification
The first line contains two integers and
– the number of tree nodes and the number of operations.
The next lines describe the ball machine. Each of these lines contains one integer, the number of
a node: the
-th of these lines contains the number of node
's parent node, or
if node
is the tree
root.
Each of the next lines contains two integers and describes an operation to be performed. An
operation of type
is denoted by
1 k
where is the number of balls to be added to the machine. An
operation of type
is denoted by
2 x
where is the number of the node from which a ball is to be
removed.
It is guaranteed that all performed operations are correct: Operations will not require to add more balls than there are empty nodes in the ball machine or to remove a ball from an empty node.
Output Specification
For each operation of type , output the number of the node where the last inserted ball ended up. For each operation of type
output the number of balls that rolled down after removing the ball from the specified node.
Sample Input
8 4
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8
Sample Output
1
3
2
2
Comments