A6526 | $「BalticOI 2013」Ball Machine$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

有一个装球机器，构造可以看作是一棵树。有下面两种操作： 从根放入一个球，只要下方有空位，球会沿着树滚下。如果同时有多个点可以走，那么会选择编号最小的节点所在路径的方向。比如依次在树根 $4$ 放 $2$ 个球，第一个球会落到 $1$，第二个会落到 $3$：![ballmachine1.png](/uploads/acgo/image/36c7bf34371b02d3_5d3054cd19a4.png) 从某个位置拿走一个球，那么它上方的球会落下来。比如依次拿走 $5, 7, 8$ 三个球：![ballmachine2.png](/uploads/acgo/image/32e26e4fc11d6048_c34bb7324fcc.png)

第一行：球的个数 $N$，操作个数 $Q(N, Q \le 10^5)$ 下面 $N$ 行：第 $i$ 个节点的父亲。如果是根，则为 $0$ 接下来 $Q$ 行：op num 1. $op = 1$：在根放入 num 个球 2. $op = 2$：拿走在位置 num 的球

保证输入合法 1. $op = 1$：输出最后一个球落到了哪里 2. $op = 2$：输出拿走那个球后有多少个球会掉下来

输入 #1

输出 #1

C++ 编辑器

输入

输出