P8353 [SDOI/SXOI2022] 无处存储

滥用本题评测将封号。请注意本题非同寻常的时空限制和数据点个数。

小 Ω 想出一个数据结构题，于是它先造了一棵点有点权的树： 给定一棵大小为 $n$ 的树，编号 $1$ 到 $n$，第 $i \in [2,n]$ 个点的父节点记作 $f_i \in [1, i-1]$。另外，每个点 $i$ 有一个点权 $a_i$，初始点权由输入确定，具体方式见输入格式。 在数据结构题里面，需要有对应的修改和查询的操作，而树上最简单的两种非平凡操作当然是链加、链求和了。 因此你需要支持以下两种操作： `0 x y v`：将树上从 $x$ 到 $y$ 的简单路径上的点的权值增加 $v$； `1 x y`：求树上从 $x$ 到 $y$ 的简单路径上的点的权值和； 出完之后小 Ω 拿给小 N 看，小 N 表示： ……这也太简单了，这不是轻重链剖分模板题吗？！！ 小 Ω 于是想到在刚刚接触 OI 的时候了解到的时间换空间的原理，因此他决定本题的空间限制为 **64 MB**。

无

无

样例 2 ~ 样例 15 数据见下方下载链接。 以上各组样例数据中，每组数据的数据范围符合其输入的子任务编号对应的子任务的数据范围及性质（输入的子任务编号为 0 时除外），并且为了避免可能的常数问题，保证下发样例（子任务编号为 0 时除外）与最终评测所用的该子任务的测试点的数据生成方式强度相同。 | 子任务编号 | 测试点分值 | $n \leq$ | $q \leq $ | 树的形态 | 特殊性质 | | :--------: | :--------: | :-------------: | :-------------: | :------: | :------: | | 1 | 2 | $3000$ | $3000$ | C | W | | 2 | 2 | $7 \times 10^6$ | $5 \times 10^4$ | A | W | | 3 | 2 | $1 \times 10^6$ | $5 \times 10^4$ | B | Y | | 4 | 2 | $2 \times 10^6$ | $5 \times 10^4$ | B | Y | | 5 | 2 | $3 \times 10^6$ | $5 \times 10^4$ | B | Y | | 6 | 2 | $4 \times 10^6$ | $5 \times 10^4$ | B | Y | | 7 | 2 | $5 \times 10^6$ | $5 \times 10^4$ | B | Y | | 8 | 2 | $6 \times 10^6$ | $5 \times 10^4$ | B | Y | | 9 | 3 | $7 \times 10^6$ | $5 \times 10^4$ | B | Y | | 10 | 2 | $1 \times 10^6$ | $5 \times 10^4$ | B | W | | 11 | 2 | $2 \times 10^6$ | $5 \times 10^4$ | B | W | | 12 | 2 | $3 \times 10^6$ | $5 \times 10^4$ | B | W | | 13 | 2 | $4 \times 10^6$ | $5 \times 10^4$ | B | W | | 14 | 2 | $5 \times 10^6$ | $5 \times 10^4$ | B | W | | 15 | 2 | $6 \times 10^6$ | $5 \times 10^4$ | B | W | | 16 | 3 | $7 \times 10^6$ | $5 \times 10^4$ | B | W | | 17 | 2 | $1 \times 10^6$ | $5 \times 10^4$ | C | X | | 18 | 2 | $2 \times 10^6$ | $5 \times 10^4$ | C | X | | 19 | 2 | $3 \times 10^6$ | $5 \times 10^4$ | C | X | | 20 | 2 | $4 \times 10^6$ | $5 \times 10^4$ | C | X | | 21 | 2 | $5 \times 10^6$ | $5 \times 10^4$ | C | X | | 22 | 2 | $6 \times 10^6$ | $5 \times 10^4$ | C | X | | 23 | 3 | $7 \times 10^6$ | $5 \times 10^4$ | C | X | | 24 | 2 | $1 \times 10^6$ | $5 \times 10^4$ | C | Y | | 25 | 2 | $2 \times 10^6$ | $5 \times 10^4$ | C | Y | | 26 | 2 | $3 \times 10^6$ | $5 \times 10^4$ | C | Y | | 27 | 2 | $4 \times 10^6$ | $5 \times 10^4$ | C | Y | | 28 | 2 | $5 \times 10^6$ | $5 \times 10^4$ | C | Y | | 29 | 2 | $6 \times 10^6$ | $5 \times 10^4$ | C | Y | | 30 | 3 | $7 \times 10^6$ | $5 \times 10^4$ | C | Y | | 31 | 2 | $1 \times 10^6$ | $5 \times 10^4$ | C | Z | | 32 | 2 | $2 \times 10^6$ | $5 \times 10^4$ | C | Z | | 33 | 2 | $3 \times 10^6$ | $5 \times 10^4$ | C | Z | | 34 | 2 | $4 \times 10^6$ | $5 \times 10^4$ | C | Z | | 35 | 2 | $5 \times 10^6$ | $5 \times 10^4$ | C | Z | | 36 | 2 | $6 \times 10^6$ | $5 \times 10^4$ | C | Z | | 37 | 3 | $7 \times 10^6$ | $5 \times 10^4$ | C | Z | | 38 | 3 | $1 \times 10^6$ | $5 \times 10^4$ | C | W | | 39 | 3 | $2 \times 10^6$ | $5 \times 10^4$ | C | W | | 40 | 3 | $3 \times 10^6$ | $5 \times 10^4$ | C | W | | 41 | 3 | $4 \times 10^6$ | $5 \times 10^4$ | C | W | | 42 | 3 | $5 \times 10^6$ | $5 \times 10^4$ | C | W | | 43 | 3 | $6 \times 10^6$ | $5 \times 10^4$ | C | W | | 44 | 3 | $7 \times 10^6$ | $5 \times 10^4$ | C | W | 上表“树的形态”一栏中，$\texttt{A}$ 代表 $\forall i \in [2,n]$，$f_i$ 在 $[1,i-1]$ 中均匀随机生成；$\texttt{B}$ 代表 $\forall i \in [2,n]$，$f_i=i-1$；$\texttt{C}$ 代表树的形态无特殊限制。 上表“特殊性质”一栏中，$\texttt{X}$ 代表没有修改操作；$\texttt{Y}$ 代表对于每次修改操作 $x=y$；$\texttt{Z}$ 代表每次询问操作 $x=y$；$\texttt{W}$ 代表无特殊性质。 对于 $100\%$ 的数据，$1 \leq n \leq 7 \times 10^6,1 \leq q \leq 5 \times 10^4,1 \leq f_i