逆向生长 - 题目

内存限制：1024 MiB 时间限制：3000 ms 标准输入输出

题目类型：传统评测方式：文本比较

上传者： PaperCloud

提交提交记录统计测试数据讨论

你平时会怎样画一棵树？我想你会先画出根节点，接着向下延伸出几条边，连向它的儿子节点，然后继续向下，画出孙子节点……

如果这一切颠倒过来，会发生什么？

现在你有一棵逆向生长的树，这棵树有个叶子节点，编号依次为。一开始，你只有这个叶子节点，你将依次处理个操作，操作分为如下两种：

注意：在次操作之后，所有节点不一定连通。

本题输入采用强制在线，具体细节请见【输入格式】。

第一行一个整数（）表示树叶子节点的个数。假设这棵树一共有（）个节点。

第二行个整数，（）。

第三行一个整数（，），表示操作个数，为计算系数。定义函数，其中为上次的操作输出的答案，初始情况。

接下来行，每行表示一个操作，其中第行第一个数为：

若，则接下来为两个整数（），然后为个整数；
- 该操作为新增一个节点，其编号为；
- 表示的儿子节点的个数；
- 的儿子节点为，其中；
若，则接下来为两个整数；
- 该操作为询问当前的 LCA 节点编号，其中；
- 如果此时不连通，请输出 0；
- 设当前询问的输出结果为，则当前操作之后，将修改为。

对于所有输入中的等，保证其取值范围为。

对于每个的询问，输出一行，其中包含一个整数，表示该询问的答案。

4
4 10 7 5
10 1 0
1 2 1 7
2 10 4
1 3 1 2
1 1 4 4 10 3 5
2 7 7
1 9 1 1
2 9 10
1 8 1 9
1 6 1 8
2 6 7

对于 30% 的数据：；

对于 50% 的数据：；

另有 25% 的数据：。（即，那么，可以发现，该部分输入不强制在线）；

对于 100% 的数据：。

提示：由于输出量过大，请不要使用过慢的输入输出方式（如未关同步的 cin/cout）。

编辑器加载中 …

或者，上传代码文件

#12607. 逆向生长