#P5346. 【XR-1】柯南家族

    ID: 4823 远端评测题 1000~4000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>倍增离散化O2优化主席树可持久化后缀数组,SA

【XR-1】柯南家族

题目背景

xht37 最近沉迷于名侦探柯南。

在某集中,小兰又在怀疑柯南的真实身份了。为了让小兰不再怀疑,柯南编造出自己的家族背景来应对小兰的询问。

题目描述

这个家族一开始只有一个人,后来不断有人有了孩子,直到现在,这个家族有 nn 个人,第 nn 个人正是柯南。易知这个家族构成了一个 nn 个点的树形结构。

柯南为了使自己编造的家庭背景更加真实,他给家族中的每个人赋予了一个智商值。但是,一个人的聪明程度不仅仅只与他的智商值有关,还可能与他祖先的聪明程度及他出生的时代有关。

具体来说,在这个家族中,A 比 B 聪明当且仅当 A 和 B 满足下面三种情况中的某一种:

  1. A 的智商值比 B 的智商值高;

  2. A 的智商值与 B 的智商值一样且 A 和 B 有不同的父亲,A 的父亲比 B 的父亲聪明;

  3. A 的智商值与 B 的智商值一样且 A 和 B 的父亲是同一个人或某一个人没有父亲,A 比 B 后出生。

有一个很显然的结论是,这个家族中不会有两个人一样聪明。

柯南需要回答小兰的 qq 个询问。为了方便说明,假设第 ii 个出生的人编号为 ii

每个询问是下面三种情况中的某一种:

  1. 1 x:询问编号为 xx 的人在整个家族中聪明程度排第几。

  2. 2 x k:询问编号为 xx 的人及其祖先中第 kk 聪明的人的编号。

  3. 3 x k:询问编号为 xx 的人及其后代中第 kk 聪明的人的编号。

柯南还有许多案子要办,他不想在回答小兰的问题上浪费时间,他希望你能编程帮他回答小兰的所有询问。

输入格式

11 行包含两个数 n,qn, q,分别表示人数和询问次数。

22 行包含 n1n-1 个数 f2nf_{2 \dots n},其中 fif_i 表示 ii 的父亲。

33 行包含 nn 个数 a1na_{1 \dots n},其中 aia_i 表示 ii 的智商值。

接下来 qq 行每行两个或三个数表示一个合法询问,其中第一个数表示询问种类,后面一个或两个数为询问参数。

输出格式

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

5 11
1 1 3 2
1 2 2 1 1
1 1
1 2
1 3
1 4
1 5
2 4 1
2 5 3
3 1 1
3 1 2
3 1 3
3 1 4
5
2
1
3
4
3
1
3
2
4
5

提示

【样例说明】

形成的树如下:

首先比较编号为 2,32,3 的两个人,由于** 33 号的智商值与 22 号的智商值一样且他们的父亲是同一个人,33 号比 22 号后出生**满足第 33 种情况,因此 33 号比 22 号聪明。

再比较编号为 4,54,5 的两个人,由于** 44 号的智商值与 55 号的智商值一样且他们有不同的父亲,44 号的父亲 33 号比 55 号的父亲 22 号聪明**满足第 22 种情况,因此 44 号比 55 号聪明。

再比较编号为 1,51,5 的两个人,由于** 55 号的智商值与 11 号的智商值一样且 11 号没有父亲,55 号比 11 号后出生**满足第 33 种情况,因此 55 号比 11 号聪明。

再根据第 11 种情况比较编号为 2,42,4 的两个人,可对 55 人的聪明程度排序:3>2>4>5>13 > 2 > 4 > 5 > 1

【数据规模与约定】

一共 1010 个测试点。

对于前 20%20\% 的数据,1n,q1031 \le n, q \le 10 ^ 3,每个测试点 77 分,时限 1s。

对于另 20%20\% 的数据,保证一个人最多只有一个儿子,每个测试点 99 分,时限 4s。

对于另 20%20\% 的数据,1n,q1051 \le n, q \le 10 ^ 5,每个测试点 99 分,时限 1.5s。

对于另 20%20\% 的数据,保证只有第一种询问,每个测试点 1212 分,时限 1.5s。

对于 100%100\% 的数据,1n,q5×1051 \le n, q \le 5 \times 10 ^ 51ai1091 \le a_i \le 10 ^ 9,每个测试点 1313 分,时限 2.5s。