[BalticOI 2013 Day1] Ball Machine
题目描述
给定一棵树,在根节点放一些球,如果下方有空位,那么它就会往下滚到下面的节点,如果有多个节点选择,它会选择 **以其(即后文中提到的儿子节点)为根节点的子树中标号最小值最小** 的儿子节点。
从一个位置上拿走球,上面的球也会滚下来。
每次给定一些操作,分别为在根节点放若干个球,和把某个节点的球拿走,求最后的结果。
输入输出格式
输入格式
第一行两个整数 $N,Q$ 代表树的节点数和操作数。
这 $N$ 个节点编号为 $1$ 到 $N$。
接下来 $N$ 行每行一个整数第 $i$ 行代表第 $i$ 个节点的父节点。
接下来 $Q$ 行每行两个整数 $opt,num$:
- 如果 $opt=1$,代表在根节点放 $num$ 个球。
- 如果 $opt=2$,代表撤掉 $num$ 节点的球。
输出格式
每次操作后都需要输出一个结果:
- 如果 $opt=1$,输出最后一个球落到了哪里。
- 如果 $opt=2$,输出撤掉那个球会有多少个球滚下来。
输入输出样例
输入样例 #1
8 4
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8
输出样例 #1
1
3
2
2
说明
#### 数据规模与约定
对于 $100\%$ 的数据,$1 \le N,Q \le 10^5$。
对于其中 $25\%$ 的数据,每个节点的儿子节点数只可能为 $0$ 个或 $2$ 个,且所有叶子节点到根节点的距离相同。
对于另外 $30\%$ 的数据,$opt=2$ 的操作输出的总为 $0$。
对于另外 $40\%$ 的数据,只能一个 $opt=1$ 的操作。
#### 说明
翻译自 [BalticOI 2013 Day1 A Ball Machine](https://boi.cses.fi/files/boi2013_day1.pdf)。