题目描述

有 $n$ 个学生构成了一棵有根树，每个学生有一个 $\text{gpa}$。

定义一个学生所在的专业为仅保留两端学生 $\text{gpa}$ 相同的边时，这个学生所在的连通分量。

定义一个专业的怨气值是 $max(dep[a]-dep[b]+1)$ $s.t$. $a,b$是专业中的学生，$dep_{根}=0$，$dep_{w}=dep_{w的父亲}+1$。

操作 1 ：给出 $x$ 和 $y$，把学生 $x$ 的 $\text{gpa}$ 改成 $y$。

操作 2 ：给出 $x$ 和 $y$，把学生 $x$ 所在的专业中所有点 $\text{gpa}$ 改为 $y$。

操作 3 ：给出 $x$，问学生 $x$ 的 $\text{gpa}$，$x$ 所在专业的人数，$x$所在专业的怨气值。

输入格式

第一行一个数 $n$。

第二行 $n$ 个数表示每个节点的父亲，其中第 $i$ 个数 $<i$，且 $1$ 节点的父亲为 $0$。

第三行 $n$ 个数表示每个学生的 $\text{gpa}$。

第四行一个数 $m$。

之后 $m$ 行，每行一个两或三个数表示一次操作，类型如上述。

输出格式

对于每个 $3$ 操作，输出一行三个数，中间用空格隔开，依次表示：学生 $x$ 的 $\text{gpa}$，$x$ 所在专业的人数，$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

提示

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

定义 $\text{gpa}$ 共有 $c$ 种。

对于 $40\%$ 的数据，$n,m \le 1000$。

对于另外 $40\%$ 的数据，$n,m \le 10^{5}$，$c=2$，$\text{gpa}$ 的范围在 $[1,2]$ 中。

对于 $100\%$ 的数据，$n,m \le 10^5$，$c=30$，$\text{gpa}$ 的范围在 $[1,30]$ 中。

我都懒得喷 THU 了。