UOJ Logo Universal Online Judge

UOJ

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

统计

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

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

我们定义一次单旋为:

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

单旋例图

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

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

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

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

输入格式

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

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

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

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

接下来 $m$ 行,每行先输入一个整数 $opt$,保证 $1 \le opt \le 3$ 。

如果 $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

样例二至样例六

见样例数据下载。

限制与约定

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

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

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

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

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

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

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

测试点编号$n\le$特殊性质分值
$1$$1000$$0$$7$
$2$$100000$$0$$9$
$3$$100000$$1,2,3,4$$27$
$4$$100000$$2,3,4$$16$
$5$$100000$$3$$23$
$6$$100000$$5$$10$
$7$$100000$$8$

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载