P7952 [✗✓OI R1] Heavenly Movements of All Things


The Geo Archon gives you a rooted tree with root $1$. Each node has a weight $a_i$. You need to support the following operations: + $\texttt{1 u}$: Query the maximum value in the subtree rooted at $u$. + $\texttt{2 u}$: For every node in the subtree rooted at $u$, change its weight **simultaneously** to the sum of the weights of all its **children**. That is, perform $\forall x \in \operatorname{subtree}(u), a_x\gets \sum_{y\in \operatorname{son}(x)}a_y$. Here, **simultaneously** means: when updating a node, its children are considered to remain in the state before this operation is applied.

The first line contains two positive integers $n, q$, representing the size of the tree and the number of queries. The second line contains $n$ positive integers, where the $i$-th number is the initial weight $a_i$ of node $i$. The third line contains $(n-1)$ integers, where the $i$-th integer $\mathit{fa}_{i+1}$ represents the parent index of node $(i+1)$. Then follow $q$ lines, each containing two integers representing one operation. The specific format is given in the “Description”.

For each $\texttt{1}$ operation, output one integer per line as the answer.

**[Sample Explanation]** Before any modification, the weights of each node are $1,1,4,5,1,4$. After the first modification, they become $1,1,4,1,0,4$. After the second modification, they become $1,5,0,0,0,4$. [A more intuitive picture](https://www.luogu.com.cn/paste/blqun4u8) **[Constraints]** **The input size of this problem is large, so please pay attention to constant-factor optimizations.** For $100\%$ of the data, $1\le n, q \le 10^6$, $1 \le u \le n$, $0 \le a_i \le 10^9$, and $\mathit{fa}_i < i$. Below are the subtasks (a blank field means there is no special property). You must pass all test points in a subtask and all test points in the subtasks it depends on to get the score for that subtask: | Subtask ID | $n, q$ | Points | Special Properties | Dependencies | | :--------: | :----------------: | :----: | :----------------: | :----------: | | 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 | Special properties: + For test points with special property A, it is guaranteed that in every operation of type $1$, $u = 1$. + For test points with special property B, it is guaranteed that in every operation of type $2$, $u = 1$. + For test points with special property C, it is guaranteed that for all nodes $i$, $\mathit{fa}_i = i - 1$. In other words, the tree is a chain. + For test points with special property D, it is guaranteed that for all nodes $i$, $\mathit{fa}_i = 1$. In other words, the tree is a star. + For test points with special property E, it is guaranteed that the testdata is random. Here, random means that operations $\texttt{1}$ and $\texttt{2}$ appear with equal probability, $u$ is chosen uniformly at random from $[1, n]$, and $\mathit{fa}_i$ is chosen uniformly at random from $[1, i - 1]$. **Hint: Since the problem setter is very lazy and Luogu cannot upload too many test points, the testdata of this problem may be relatively weak. Also, to avoid longer running time due to heavy load on the contest judge machines, the time limit has been relaxed. Therefore, everyone is welcome to try passing this problem with strange hacky approaches.** > May we cleanse the four directions, and guard a corner of the mortal world. Translated by ChatGPT 5