#139. 树链剖分
题目描述
这是一道模板题。
给定一棵 $n$个节点的树，初始时该树的根为 111 号节点，每个节点有一个给定的权值。下面依次进行 $m$ 个操作，操作分为如下五种类型：
-
换根：将一个指定的节点设置为树的新根。
-
修改路径权值：给定两个节点，将这两个节点间路径上的所有节点权值（含这两个节点）增加一个给定的值。
-
修改子树权值：给定一个节点，将以该节点为根的子树内的所有节点权值增加一个给定的值。
-
询问路径：询问某条路径上节点的权值和。
-
询问子树：询问某个子树内节点的权值和
输入格式
第一行为一个整数 n，表示节点的个数。
第二行 n 个整数表示第 iii 个节点的初始权值 $a_i$。
第三行 n−1 个整数，表示 i+1i+1i+1 号节点的父节点编号$ fi+1 (1⩽fi+1⩽n)f_{i+1}\ (1 \leqslant f_{i+1} \leqslant n)fi+1 (1⩽fi+1⩽n)。$
第四行一个整数 m，表示操作个数。
接下来 m 行，每行第一个整数表示操作类型编号：$(1⩽u,v⩽n)(1 \leqslant u, v \leqslant n)(1⩽u,v⩽n)$
-
若类型为 111，则接下来一个整数 u，表示新根的编号。
-
若类型为 222，则接下来三个整数 u,v,ku,v,ku,v,k，分别表示路径两端的节点编号以及增加的权值。
-
若类型为 333，则接下来两个整数 u,ku,ku,k，分别表示子树根节点编号以及增加的权值。
-
若类型为 444，则接下来两个整数 u,vu,vu,v，表示路径两端的节点编号。
-
若类型为 555，则接下来一个整数 u，表示子树根节点编号。
输出格式
对于每一个类型为 444 或 555 的操作，输出一行一个整数表示答案。
样例
样例输入
61 2 3 4 5 61 2 1 4 464 5 62 2 4 15 11 43 1 24 2 5
样例输出
152419
数据范围与提示
对于 $100%100\%100%$ 的数据，$1⩽n,m,k,ai⩽1051\leqslant n,m,k,a_i\leqslant 10^51⩽n,m,k,ai⩽105$。数据有一定梯度。
题意：树链加，子树加，需要支持换根，查询树链和，子树和
题解：
树链剖分模板，树链加和查询直接树链剖分即可，
注意到树链剖分有个很方便的性质就是链剖的序列其实也是dfs序，记录一个点的序列上起点和终点就可以顺便维护子树，
换根的话分类讨论一下，一直以1号点为根，对树链的修查无影响，考虑子树：
假设访问u号点，在以1号点为根的形态下：
当前根rt，如果u==rt则u的子树为整个以1为根的树，
如果rt是u的子树里的节点，那么u所代表的的子树就是整个子树 - rt的祖先里u的儿子的 子树 ，
如果rt不是u的子树里的节点，那么u的子树就是以1为根时u的子树；
这样操作后也是区间，可以和前两个一起维护；
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include