Background

Luogu’s testdata is only for non-official communication and is not official testdata. Official judging link: https://www.cspro.org/.

Problem Description

Little C, who has just joined Xixi Eiffel Island Co., Ltd., has taken over the project from Little S, who was just promoted. However, when Little C opened the project, the layers of nested folders made Little C feel dizzy. To simplify the project structure, Little C decided to perform some necessary merges on the project folders.

There are $n$ folders in the project. For convenience, we number these $n$ folders with integers from $1$ to $n$, where folder $1$ is the root folder of the project. Every other folder has exactly one parent folder, and these folders form a tree structure. Besides subfolders, folder $i$ also directly stores $d_i$ bytes of data.

Little C performed several folder merge operations. In each operation, Little C chooses a folder $x_j$ and merges this folder together with all its subfolders. Specifically, Little C does the following: for each child folder $y$ of $x_j$, move all folders and files contained in folder $y$ into folder $x_j$, and then delete folder $y$. All file and folder names are pairwise distinct, so there is no need to consider name conflicts during merging. After each merge operation, Little C needs to know how many folders and how many bytes of data are contained in folder $x_j$.

For example, consider the following project: the root folder contains folder $2$ and folder $3$ and $100$ bytes of data, where folder $2$ is empty, and folder $3$ contains $200$ bytes of data and folder $4$, and folder $4$ contains $300$ bytes of data. After one merge on the root folder, folder $2$ and folder $3$ are merged into the root folder. Now under the root folder there is folder $4$ and $300$ bytes of data, and folder $4$ also contains $300$ bytes of data.

During the merging process, Little C often needs to access files under some folder $z_j$. At this time, Little C starts from the root folder and each time enters one child folder of the current folder. Little C needs to know, following the above process, what is the minimum number of folders that must be passed through to reach the files under folder $z_j$.

For example, in the above project, before merging the root folder, accessing files under the root folder only requires passing through the root folder, while accessing folder $4$ requires passing through the root folder as well as folder $3$ and $4$. After merging the root folder, accessing folder $4$ only requires passing through the root folder and folder $4$.

In the whole project, Little C performed a total of $m$ folder merge and file access operations. You need to help Little C correctly maintain the relationships between folders, and after each operation, correctly answer the required data.

Input Format

Read input from standard input.

The first line contains two integers $n, m$, representing the number of folders and the number of operations.

The second line contains $(n - 1)$ integers $f_2, \cdots , f_n$, where $f_i$ is the index of the parent folder of folder $i$.

The third line contains $n$ integers $d_1, d_2, \cdots , d_n$, where $d_i$ is the amount of data stored in folder $i$.

Then follow $m$ lines. On line $j$, there are two integers. The first integer $op_j$ indicates the operation type. If $op_j = 1$, it indicates a folder merge operation, followed by an integer $x_j$ which is the index of the folder to be merged; if $op_j = 2$, it indicates a file access operation, followed by an integer $z_j$ which is the index of the folder to be accessed.

Output Format

Write output to standard output.

Output $m$ lines. Line $j$ describes the data Little C needs for the $j$-th operation: if $op_j = 1$, output two integers, in order, the number of subfolders of folder $x_j$ and the amount of stored data; if $op_j = 2$, output one integer, the minimum number of folders Little C needs to pass through to obtain the data under folder $z_j$.

4 6
1 1 3
100 0 200 300
2 1
2 4
1 1
2 4
1 1
1 1

1
3
1 300
2
0 600
0 600

Hint

Subtasks

For all testdata,

• $1 \le n \le 5 \times 10^5, 1 \le m \le 3 \times n$,
• $1 \le f_i \le n$, the input folder structure forms a tree,
• $0 \le d_i \le 10^5$,
• $1 \le x_j, z_j \le n$, in each merge operation, the given folder $x_j$ is not deleted, and in each file access operation, the given folder $z_j$ is not deleted.

Special Property A: $f_i = (i - 1)$.

Special Property B: $f_i = 1$.

Special Property C: in folder merge operations, $x_j = 1$.

Special Property D: $op_j = 1$, i.e. there are no file access operations.

Special Property E: $op_j = 2$, i.e. there are no folder merge operations.

Translated by ChatGPT 5