U211180 【模板】树链剖分（加强版）

这是 [LOJ #139](https://loj.ac/p/139) 的一个非官方、不维护的镜像。 同时也是 [P3384](https://www.luogu.com.cn/problem/P3384) 的加强版

这是一道模板题。 给定一棵 $n$ 个节点的树，初始时该树的根为 $1$ 号节点，每个节点有一个给定的权值。下面依次进行 个操作，操作分为如下五种类型： - 换根：将一个指定的节点设置为树的新根。 - 修改路径权值：给定两个节点，将这两个节点间路径上的所有节点权值（含这两个节点）增加一个给定的值。 - 修改子树权值：给定一个节点，将以该节点为根的子树内的所有节点权值增加一个给定的值。 - 询问路径：询问某条路径上节点的权值和。 - 询问子树：询问某个子树内节点的权值和。

第一行一个整数 $n$，表示节点的个数。 第二行 $n$ 个整数表示第 $i$ 个节点的初始权值 $a_i$ 第三行 $n-1$ 个整数，表示 $i+1$ 号节点的父节点编号 $f_{i+1}\ (1\leqslant f_{i+1} \leqslant n)$ 第四行一个整数 $m$，表示操作个数。 接下来 $m$ 行，每行第一个整数表示操作类型编号：$(1 \leqslant u,v \leqslant n)$ - 若类型为 $1$，则接下来一个整数 $u$，表示新根的编号。 - 若类型为 $2$，则接下来三个整数 $u,v,k$，分别表示路径两端的节点编号以及增加的权值。 - 若类型为 $3$，则接下来两个整数 $u,k$，分别表示子树根节点编号以及增加的权值。 - 若类型为 $4$，则接下来两个整数 $u,v$，表示路径两端的节点编号。 - 若类型为 $5$，则接下来一个整数 $u$，表示子树根节点编号。

对于每一个类型为 $4$ 或 $5$ 的操作，输出一行一个整数表示答案。

对于 $100\%$ 的数据，$1 \leqslant n,m \leqslant 10^5,0 \leqslant a_i,k \leqslant 10^5$。数据有一定梯度。