#748. [Baltic2013]ballmachine
[Baltic2013]ballmachine
Description
有一个装球机器,构造可以看作是一棵树。有下面两种操作:
- 从根放入一个球,只要下方有空位,球会沿着树滚下。如果同时有多个点可以走,那么会选择编号最小的节点所在路径的方向。比如依次在树根
4
放2个球,第一个球会落到1
,第二个会落到3
: - 从某个位置拿走一个球,那么它上方的球会落下来。比如依次拿走
5, 7, 8
三个球:
Format
Input
第一行:球的个数N
,操作个数Q
(N, Q <= 100 000
)下面N
行:第i
个节点的父亲。如果是根,则为0
接下来Q
行:op num
op == 1
:在根放入num
个球op == 2
:拿走在位置num
的球
Output
保证输入合法
op == 1
:输出最后一个球落到了哪里op == 2
:输出拿走那个球后有多少个球会掉下来
Samples
8 4
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8
1
3
2
2