P16035 [CSPro 33] Folder Merge.

Luogu’s testdata is only for non-official communication and is not official testdata. Official judging link: .

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.

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.

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$.

### 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. | Subtask ID | $n \le$ | Special Property | Score | |:----------:|:-----------:|:----------------:|:-----:| | 1 | 500 | None | 10 | | 2 | 5,000 | ^ | 15 | | 3 | $10^5$ | ^ | ^ | | 4 | $5 \times 10^5$ | A | 5 | | 5 | ^ | B | ^ | | 6 | ^ | C | 10 | | 7 | ^ | D | 15 | | 8 | ^ | E | 10 | | 9 | ^ | None | 15 | 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