P7952 [✗✓OI R1] 天动万象
题目背景
题目描述
帝君给了你一棵以 $1$ 为根的有根树，每个点有一个点权 $a_i$，要求支持以下几种操作：
+ $\texttt{1 u}$ 表示查询以 $u$ 为根的子树的最大值。
+ $\texttt{2 u}$ 表示将 $u$ 为根的子树内每一个节点的权值 **同时变为** 其所有 **儿子** 的权值之和，即对这棵子树执行 $\forall x \in \operatorname{subtree}(u), a_x\gets \sum_{y\in \operatorname{son}(x)}a_y$。其中 **同时变为** 的意思是「某个点操作时认为其儿子停留在这次操作未进行前的状态」。
输入格式
第一行两个正整数 $n,q$ 表示树的大小和询问组数。
第二行 $n$ 个正整数，第 $i$ 个数表示表示第 $i$ 个点的初始点权 $a_i$。
第三行 $(n-1)$ 个整数，其中第 $i$ 个整数 $\mathit{fa}_{i+1}$ 表示第 $(i+1)$ 个节点的父亲编号。
接下来 $q$ 行，每行两个整数表示一次操作，具体格式见「题目描述」。
输出格式
对于每次 $\texttt{1}$ 操作输出一行一个整数表示答案。
说明/提示
**【样例解释】**
修改前每个点的权值分别为 $1,1,4,5,1,4$。
第一次修改后变为 $1,1,4,1,0,4$。
第二次修改后变为 $1,5,0,0,0,4$。
[更直观的图片](https://www.luogu.com.cn/paste/blqun4u8)
**【数据范围】**
**本题数据量较大，请注意常数优化。**
对于 $100\%$ 的数据，满足 $1\le n, q \le 10^6$，$1 \le u \le n$，$0 \le a_i \le 10^9$，$\mathit{fa}_i < i$。
以下是子任务（留空则表示无特殊性质），你必须通过一个子任务中的所有测试点以及该子任务依赖的所有测试点，才能获得这个子任务的分数：
| 子任务编号 | $n, q$ | 子任务总分 | 特殊性质 | 依赖子任务 |
| :--------: | :----------------: | :------: | :------: | :--------: |
| 0 | $\le 5\times 10^3$ | 3 | E | |
| 1 | $\le 10^5$ | 6 | A, B | |
| 2 | | 8 | C | |
| 3 | | 4 | D | |
| 4 | | 13 | E | Subtask0 |
| 5 | | 36 | B | Subtask1 |
| 6 | | 30 | | Subtask0~5 |
特殊性质：
+ 对于满足特殊性质 A 的测试点，保证每次 $1$ 操作 $u=1$。
+ 对于满足特殊性质 B 的测试点，保证每次 $2$ 操作 $u=1$。
+ 对于满足特殊性质 C 的测试点，保证对于所有节点 $i$， 满足 $\mathit{fa}_i=i-1$，换句话说树的形态是一条链。
+ 对于满足特殊性质 D 的测试点，保证对于所有节点 $i$， 满足 $\mathit{fa}_i=1$，换句话说树的形态是一个菊花。
+ 对于满足特殊性质 E 的测试点，保证数据随机，这里的数据随机指 $\texttt{1}$ 操作和 $\texttt{2}$ 操作等概率出现，$u$ 在 $[1, n]$ 内等概率随机，$\mathit{fa}_i$ 在 $[1, i - 1]$ 内等概率随机。
**提示：由于出题人很懒而且洛谷传不了很多数据点，因此本题数据可能较弱，而且为了避免赛事评测机压力导致的运行时间增加，本题放宽了时限，因此欢迎大家尝试用奇怪的乱搞通过本题。**
> 只愿荡涤四方，护得浮世一隅。