UOJ Logo Universal Online Judge

UOJ

#456. 【UER #8】许愿树和圣诞树

附件下载 统计

圣诞节就要到了,小C想买一棵圣诞树。自然,请客请到破产的小C买不起圣诞树,所以,小C计划把过年用的许愿树改造成圣诞树。

许愿树是一棵 n 个节点的二叉搜索树n 个节点的权值为 1n 的排列。

我们定义一次单旋为:

假设 x 是其父亲 p 的左孩子。我们对它做下图操作,则称为一次单旋。

单旋例图

如果是右孩子,就做其轴对称操作。

圣诞树支持如下三个操作:

  1. x 连续不断单旋向上,直至它成为点 y 的儿子,保证 yx 的祖先
  2. 询问点 x 的第 k 级祖先,保证此时点 x 的第 k 级祖先存在
  3. 询问整棵树先序遍历中的第 k 个点,保证此时1kn

许愿树不支持这些操作,现在小C希望你能帮助他加上这些功能。

输入格式

第一行一个正整数 n 表示许愿树的节点数。

第二行 n 个正整数,记第 i 个整数 fi 表示权值为 i 的节点的父亲。

如果 fi=0,表示该节点是根。 你可以通过 ifi 的相对大小来确定该节点是其父亲的左孩子还是右孩子。 保证所形成树结构是一棵二叉搜索树。

第三行一个正整数 m 表示操作次数。

接下来 m 行,每行先输入一个整数 opt,保证 1opt3

如果 opt=1 ,则之后还跟着两个正整数 x,y ,表示将点 x 连续不断单旋向上,直至它成为点 y 的儿子。

如果 opt=2 ,则之后还跟着两个正整数 x,k ,表示询问询问点 x 的第 k 级祖先。

如果 opt=3 ,表示询问整棵树先序遍历中的第 k 个点。

输出格式

输出若干行,每行一个整数表示询问的答案。

样例一

input

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

output

7
9
4
5
9
9

样例二至样例六

见样例数据下载。

限制与约定

本题采用捆绑测试,对于每个子任务,只有通过其中全部数据才可以获得分数。 对于全部数据,1n,m1000000fin

特殊性质 0:保证数据随机。

特殊性质 1:保证所有修改都在询问之前。

特殊性质 2:保证每次一操作中的点 y 都是整棵树的根。

特殊性质 3:保证没有三操作

特殊性质 4:保证所有二操作中k=1

特殊性质 5:保证没有二操作

测试点编号n特殊性质分值
1100007
210000009
31000001,2,3,427
41000002,3,416
5100000323
6100000510
71000008

时间限制1s

空间限制512MB

下载

样例数据下载