Description

There are $n$ students forming a rooted tree, and each student has a $\text{gpa}$.

Define a student’s major as the connected component that contains this student after keeping only the edges whose two endpoints have the same $\text{gpa}$.

Define the resentment value of a major as $max(dep[a]-dep[b]+1)$ $s.t$. $a,b$ are students in the major, $dep_{root}=0$, and $dep_{w}=dep_{w's\ father}+1$.

Operation 1: given $x$ and $y$, change student $x$’s $\text{gpa}$ to $y$.

Operation 2: given $x$ and $y$, change the $\text{gpa}$ of all nodes in the major containing student $x$ to $y$.

Operation 3: given $x$, ask for student $x$’s $\text{gpa}$, the number of students in the major containing $x$, and the resentment value of the major containing $x$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers representing the parent of each node. The $i$-th integer is $< i$, and the parent of node $1$ is $0$.

The third line contains $n$ integers representing each student’s $\text{gpa}$.

The fourth line contains an integer $m$.

Then follow $m$ lines. Each line contains two or three integers representing one operation, with types as described above.

Output Format

For each operation of type $3$, output one line with three integers separated by spaces, in order: student $x$’s $\text{gpa}$, the number of students in the major containing $x$, and the resentment value of the major containing $x$.

10
0 1 1 1 3 4 2 4 2 3
16 20 29 16 23 6 29 21 1 22
10
3 4
3 4
2 6 20
2 1 8
2 2 8
1 9 21
3 6
3 2
1 3 11
1 4 17

16 2 2
16 2 2
20 1 1
8 3 2

Hint

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078

Assume there are a total of $c$ kinds of $\text{gpa}$.

For $40\%$ of the testdata, $n,m \le 1000$.

For another $40\%$ of the testdata, $n,m \le 10^{5}$, $c=2$, and $\text{gpa}$ is in $[1,2]$.

For $100\%$ of the testdata, $n,m \le 10^5$, $c=30$, and $\text{gpa}$ is in $[1,30]$.

I am too lazy to even complain about THU.

Translated by ChatGPT 5