P5529 [Ynoi2012] Dream Broken SCOI2017

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

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.

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

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