#P5346. 【XR-1】柯南家族
【XR-1】柯南家族
题目背景
xht37 最近沉迷于名侦探柯南。
在某集中,小兰又在怀疑柯南的真实身份了。为了让小兰不再怀疑,柯南编造出自己的家族背景来应对小兰的询问。
题目描述
这个家族一开始只有一个人,后来不断有人有了孩子,直到现在,这个家族有 个人,第 个人正是柯南。易知这个家族构成了一个 个点的树形结构。
柯南为了使自己编造的家庭背景更加真实,他给家族中的每个人赋予了一个智商值。但是,一个人的聪明程度不仅仅只与他的智商值有关,还可能与他祖先的聪明程度及他出生的时代有关。
具体来说,在这个家族中,A 比 B 聪明当且仅当 A 和 B 满足下面三种情况中的某一种:
-
A 的智商值比 B 的智商值高;
-
A 的智商值与 B 的智商值一样且 A 和 B 有不同的父亲,A 的父亲比 B 的父亲聪明;
-
A 的智商值与 B 的智商值一样且 A 和 B 的父亲是同一个人或某一个人没有父亲,A 比 B 后出生。
有一个很显然的结论是,这个家族中不会有两个人一样聪明。
柯南需要回答小兰的 个询问。为了方便说明,假设第 个出生的人编号为 。
每个询问是下面三种情况中的某一种:
-
1 x
:询问编号为 的人在整个家族中聪明程度排第几。 -
2 x k
:询问编号为 的人及其祖先中第 聪明的人的编号。 -
3 x k
:询问编号为 的人及其后代中第 聪明的人的编号。
柯南还有许多案子要办,他不想在回答小兰的问题上浪费时间,他希望你能编程帮他回答小兰的所有询问。
输入格式
第 行包含两个数 ,分别表示人数和询问次数。
第 行包含 个数 ,其中 表示 的父亲。
第 行包含 个数 ,其中 表示 的智商值。
接下来 行每行两个或三个数表示一个合法询问,其中第一个数表示询问种类,后面一个或两个数为询问参数。
输出格式
输出 行,每行一个数表示询问的答案。
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
提示
【样例说明】
形成的树如下:
首先比较编号为 的两个人,由于** 号的智商值与 号的智商值一样且他们的父亲是同一个人, 号比 号后出生**满足第 种情况,因此 号比 号聪明。
再比较编号为 的两个人,由于** 号的智商值与 号的智商值一样且他们有不同的父亲, 号的父亲 号比 号的父亲 号聪明**满足第 种情况,因此 号比 号聪明。
再比较编号为 的两个人,由于** 号的智商值与 号的智商值一样且 号没有父亲, 号比 号后出生**满足第 种情况,因此 号比 号聪明。
再根据第 种情况比较编号为 的两个人,可对 人的聪明程度排序:。
【数据规模与约定】
一共 个测试点。
对于前 的数据,,每个测试点 分,时限 1s。
对于另 的数据,保证一个人最多只有一个儿子,每个测试点 分,时限 4s。
对于另 的数据,,每个测试点 分,时限 1.5s。
对于另 的数据,保证只有第一种询问,每个测试点 分,时限 1.5s。
对于 的数据,,,每个测试点 分,时限 2.5s。