7768: 【模板题】树链剖分
[Creator : ]
Description
这是一道模板题。
给定一棵 n 个节点的树，初始时该树的根为 1 号节点，每个节点有一个给定的权值。下面依次进行 m 个操作，操作分为如下五种类型：
给定一棵 n 个节点的树，初始时该树的根为 1 号节点，每个节点有一个给定的权值。下面依次进行 m 个操作，操作分为如下五种类型：
-
换根：将一个指定的节点设置为树的新根。
-
修改路径权值：给定两个节点，将这两个节点间路径上的所有节点权值（含这两个节点）增加一个给定的值。
-
修改子树权值：给定一个节点，将以该节点为根的子树内的所有节点权值增加一个给定的值。
-
询问路径：询问某条路径上节点的权值和。
-
询问子树：询问某个子树内节点的权值和。
Input
第一行一个整数 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)$
第二行 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，分别表示路径两对于每一个类型为 4 或 5 的操作，输出一行一个整数表示答案。端的节点编号以及增加的权值。
-
若类型为 3，则接下来两个整数 u,k，分别表示子树根节点编号以及增加的权值。
-
若类型为 4，则接下来两个整数 u,v，表示路径两端的节点编号。
-
若类型为 5，则接下来一个整数 u，表示子树根节点编号。
Output
对于每一个类型为 4 或 5 的操作，输出一行一个整数表示答案。
Constraints
对于 $100\%$ 的数据，$1\leqslant n,m\leqslant 10^5,0\leqslant a_i,k\leqslant 10^5$。数据有一定梯度。
Sample 1 Input
6
1 2 3 4 5 6
1 2 1 4 4
6
4 5 6
2 2 4 1
5 1
1 4
3 1 2
4 2 5
Sample 1 Output
15
24
19