P5346 [XR-1] Conan Family

xht37 has recently been addicted to *Detective Conan*. In one episode, Ran suspects Conan’s true identity again. To stop Ran from suspecting him, Conan makes up a family background to answer Ran’s questions.

This family initially has only one person. Later, people keep having children, and up to now the family has $n$ people. Person $n$ is Conan. It is easy to see that this family forms a tree structure with $n$ nodes. To make his made-up family background more realistic, Conan assigns each person an **IQ value**. However, a person’s **smartness** is not only related to their **IQ value**, but may also depend on their **ancestors’ smartness** and the **era when they were born**. Specifically, in this family, A is smarter than B **if and only if** A and B satisfy one of the following three conditions: 1. A’s IQ value is higher than B’s IQ value. 2. A’s IQ value equals B’s IQ value, and A and B have different fathers; A’s father is smarter than B’s father. 3. A’s IQ value equals B’s IQ value, and A and B have the same father or one of them has no father; A is born later than B. An obvious conclusion is that no two people in this family are equally smart. Conan needs to answer Ran’s $q$ queries. For convenience, assume the $i$-th person to be born is numbered $i$. Each query is one of the following three types: 1. `1 x`: Ask what rank (in terms of smartness) the person numbered $x$ has in the whole family. 2. `2 x k`: Ask for the number of the $k$-th smartest person among person $x$ and all their ancestors. 3. `3 x k`: Ask for the number of the $k$-th smartest person among person $x$ and all their descendants. Conan still has many cases to solve and does not want to waste time answering Ran’s questions. He hopes you can write a program to help him answer all queries.

The first line contains two integers $n, q$, representing the number of people and the number of queries. The second line contains $n - 1$ integers $f_{2 \dots n}$, where $f_i$ denotes the father of $i$. The third line contains $n$ integers $a_{1 \dots n}$, where $a_i$ denotes the IQ value of $i$. The next $q$ lines each contain two or three integers describing a valid query. The first integer is the query type, and the following one or two integers are the query parameters.

Output $q$ lines, each containing one integer representing the answer to the query.

[Sample Explanation] The formed tree is as follows:  First compare persons $2$ and $3$. Since **person $3$ has the same IQ value as person $2$ and they have the same father, and person $3$ is born later than person $2$**, condition 3 is satisfied, so person $3$ is smarter than person $2$. Then compare persons $4$ and $5$. Since **person $4$ has the same IQ value as person $5$ and they have different fathers, and person $4$’s father (person $3$) is smarter than person $5$’s father (person $2$)**, condition 2 is satisfied, so person $4$ is smarter than person $5$. Then compare persons $1$ and $5$. Since **person $5$ has the same IQ value as person $1$ and person $1$ has no father, and person $5$ is born later than person $1$**, condition 3 is satisfied, so person $5$ is smarter than person $1$. Then, using condition 1 to compare persons $2$ and $4$, we can sort the smartness of the $5$ people as: $3 > 2 > 4 > 5 > 1$. [Constraints] There are $10$ test points in total. For the first $20\%$ of the data, $1 \le n, q \le 10 ^ 3$. Each test point is worth $7$ points, time limit 1 s. For another $20\%$ of the data, each person has at most one son. Each test point is worth $9$ points, time limit 4 s. For another $20\%$ of the data, $1 \le n, q \le 10 ^ 5$. Each test point is worth $9$ points, time limit 1.5 s. For another $20\%$ of the data, only the first type of query is guaranteed. Each test point is worth $12$ points, time limit 1.5 s. For $100\%$ of the data, $1 \le n, q \le 5 \times 10 ^ 5$, $1 \le a_i \le 10 ^ 9$. Each test point is worth $13$ points, time limit 2.5 s. Translated by ChatGPT 5