* 树链剖分模板题

* 由于存在换根操作

* 对所有关于节点 u 的修改和查询操作进行分类讨论

* 若 Root 在 u 的子树中，则不处理 u 所在的 Root 的那颗子树

* 否则不会有影响

* 寻找 Root 所在的那颗子树的根可以用倍增求

#include 
     
      const int N = 1e5 + 10;#define LL long longint topp[N], fa[N], size[N], son[N], deep[N], tree[N], lst[N], rst[N], bef[N], data[N];int f[N][30];int Tree;LL W[N << 2], F[N << 2], S[N << 2];struct Node {    int u, v, nxt;} G[N << 1];int now, head[N];int n, m, Root;int opt, T;#define gc getchar()inline int read() {     int x = 0; char c = gc;    while(c < '0' || c > '9') c = gc;    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;    return x;}void Add(int u, int v) {G[++ now].v = v; G[now].nxt = head[u]; head[u] = now;}void Dfs_1(int u, int f_, int dep) {    fa[u] = f_, deep[u] = dep, size[u] = 1;    for(int i = head[u]; ~ i; i = G[i].nxt) {        int v = G[i].v;        if(v == f_) continue;        f[v][0] = u;        Dfs_1(v, u, dep + 1);        size[u] += size[v];        if(size[son[u]] < size[v]) son[u] = v;    }}void Dfs_2(int u, int tp) {    topp[u] = tp, tree[u] = ++ Tree, bef[Tree] = u, lst[u] = Tree;    if(!son[u]) {        rst[u] = Tree; return ;    }    Dfs_2(son[u], tp);    for(int i = head[u]; ~ i; i = G[i].nxt) {        int v = G[i].v;        if(v != fa[u] && v != son[u]) Dfs_2(v, v);    }    rst[u] = Tree;}void Before() {    for(int i = 1; (1 << i) <= n; i ++)        for(int j = 1; j <= n; j ++)            if(f[j][i - 1]) f[j][i] = f[f[j][i - 1]][i - 1];}#define lson jd << 1#define rson jd << 1 | 1void Build_tree(int l, int r, int jd) {    S[jd] = (r - l + 1);    if(l == r) {        W[jd] = data[bef[l]];        return ;    }    int mid = (l + r) >> 1;    Build_tree(l, mid, lson);    Build_tree(mid + 1, r, rson);    W[jd] = W[lson] + W[rson];}void Pushdown(int jd) {    if(!F[jd]) return ;    F[lson] += F[jd];    F[rson] += F[jd];    W[lson] += (S[lson] * F[jd]);    W[rson] += (S[rson] * F[jd]);    F[jd] = 0;} void Sec_G(int l, int r, int jd, int x, int y, int num) {    if(x <= l && r <= y) {        F[jd] += num;        W[jd] += (S[jd] * num);        return ;    }    Pushdown(jd);    int mid = (l + r) >> 1;    if(x <= mid) Sec_G(l, mid, lson, x, y, num);    if(y >  mid) Sec_G(mid + 1, r, rson, x, y, num);    W[jd] = W[lson] + W[rson];}void Sec_G_imp(int x, int y, int num) {    int tpx = topp[x], tpy = topp[y];    while(tpx != tpy) {        if(deep[tpx] < deep[tpy]) std:: swap(tpx, tpy), std:: swap(x, y);        Sec_G(1, n, 1, tree[tpx], tree[x], num);        x = fa[tpx];        tpx = topp[x];    }    if(deep[x] < deep[y]) std:: swap(x, y);    Sec_G(1, n, 1, tree[y], tree[x], num);    return ;}inline int Find(int x, int y) {    int dy = deep[y], dx = deep[x];    int del = deep[y] - deep[x] - 1;    for(int i = 0; (1 << i) <= del; i ++)        if(del & (1 << i)) y = f[y][i];    return y;}LL Answer;void Sec_A(int l, int r, int jd, int x, int y) {    if(x <= l && r <= y) {        Answer += W[jd];        return ;    }    Pushdown(jd);    int mid = (l + r) >> 1;    if(x <= mid) Sec_A(l, mid, lson, x, y);    if(y > mid)  Sec_A(mid + 1, r, rson, x, y);}LL Sec_A_imp(int x, int y) {    int tpx = topp[x], tpy = topp[y];    LL ret = 0;    while(tpx != tpy) {        if(deep[tpx] < deep[tpy]) std:: swap(tpx, tpy), std:: swap(x, y);        Answer = 0;        Sec_A(1, n, 1, tree[tpx], tree[x]);        ret += Answer;        x = fa[tpx];        tpx = topp[x];    }    if(deep[x] < deep[y]) std:: swap(x, y);    Answer = 0;    Sec_A(1, n, 1, tree[y], tree[x]);    ret += Answer;    return ret;}int main() {    Root = 1;    n = read();    for(int i = 1; i <= n; i ++) head[i] = -1;    for(int i = 1; i <= n; i ++) data[i] = read();    for(int i = 1; i < n; i ++) {        int u = read();        Add(i + 1, u), Add(u, i + 1);    }    Dfs_1(1, 0, 1);    Dfs_2(1, 1);    Build_tree(1, n, 1);    Before();    int t = read();    for(T = 1; T <= t; T ++) {        opt = read();        if(opt == 1) Root = read();        else if(opt == 2) {            int u = read(), v = read(), x = read();            Sec_G_imp(u, v, x);        } else if(opt == 3) {            int u = read(), x = read();            if(Root == u) {                Sec_G(1, n, 1, 1, n, x);                continue;            }            if(lst[u] <= tree[Root] && tree[Root] <= rst[u]) {                Sec_G(1, n, 1, 1, n, x);                int Use_son = Find(u, Root);                Sec_G(1, n, 1, lst[Use_son], rst[Use_son], -x);            } else Sec_G(1, n, 1, lst[u], rst[u], x);        } else if(opt == 4) {            int x = read(), y = read();            printf("%lld\n", Sec_A_imp(x, y));        } else {            int u = read();            if(Root == u) {                Answer = 0;                Sec_A(1, n, 1, 1, n);                printf("%lld\n", Answer);                continue;            }            LL Now_ans = 0;            if(lst[u] <= tree[Root] && tree[Root] <= rst[u]) {                Answer = 0;                Sec_A(1, n, 1, 1, n);                Now_ans += Answer;                int Use_son = Find(u, Root);                Answer = 0;                Sec_A(1, n, 1, lst[Use_son], rst[Use_son]);                Now_ans -= Answer;            } else {                Answer = 0;                Sec_A(1, n, 1, lst[u], rst[u]);                Now_ans += Answer;            }            printf("%lld\n", Now_ans);        }    }    return 0;}