10分求助

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define cal int mid = (l + r) / 2,lchild = root * 2,rchild = root * 2 + 1;
const int N = 1e5 + 5e4;
int n,m,r,p,vistime;
int a[N],fa[N],w_child[N],siz[N],top[N],dfn[N],rdfn[N],dep[N];
int w[N << 2],tag[N << 2];
struct egde{
    int to,nex;
} e[N];
int ecnt,head[N];
void add_egde(int u,int v){
    ecnt++;
    e[ecnt] = (egde){v,head[u]};
    head[u] = ecnt;
}
void dfs1(int cur,int father){
    fa[cur] = father;
    siz[cur] = 1;
    dep[cur] = dep[father] + 1;
    for(int i = head[cur];i;i = e[i].nex){
        int v = e[i].nex;
        if(v != father){
            dfs1(v,cur);
            siz[cur] += siz[v];
            if(siz[v] > siz[w_child[cur]])
                w_child[cur] = v;
        }
    }
}
void dfs2(int cur,int Top){
    vistime++;
    dfn[cur] = vistime;
    rdfn[vistime] = cur;
    top[cur] = Top;
    if(w_child[cur]){
        dfs2(w_child[cur],Top);
        for(int i = head[cur];i;i = e[i].nex)
            if(e[i].to != fa[cur] && e[i].to != w_child[cur])
                dfs2(e[i].to,e[i].to);
    }
}
bool in_range(int L,int R,int l,int r){
    return (l <= L) && (r >= R);
}
bool out_range(int L,int R,int l,int r){
    return (L > r) || (R < l);
}
void push_up(int root){
    int lchild = root << 1,rchild = lchild + 1;
    w[root] = (w[lchild] + w[rchild]) % p;
}
void build(int root,int l,int r){
    if(l == r){
        w[root] = a[rdfn[l]];
        return;
    }
    cal
    build(lchild,l,mid);
    build(lchild,mid + 1,r);
    push_up(root);
}
void make_tag(int root,int len,int x){
    tag[root] = (tag[root] + x) % p;
    w[root] = (w[root] + len * x) % p;
}
void push_down(int root,int l,int r){
    cal
    make_tag(lchild,mid - l + 1,tag[root]);
    make_tag(rchild,r - mid,tag[root]);
    tag[root] = 0;
}
void update1(int root,int L,int R,int l,int r,int x){
    if(in_range(L,R,l,r))
        make_tag(root,R - L + 1,x);
    else if(!out_range(L,R,l,r)){
        cal
        push_down(root,L,R);
        update1(lchild,L,mid,l,r,x);
        update1(rchild,mid + 1,R,l,r,x);
        push_up(root);
    }
}
void update2(int x,int y,int z){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])
            swap(x,y);
        update1(1,1,n,dfn[top[x]],dfn[x],z);
        x = fa[top[x]];
    }
    update1(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),z);
}
int get_sum(int root,int L,int R,int l,int r){
    if(in_range(L,R,l,r))
        return w[root];
    else if(!out_range(L,R,l,r)){
        cal
        push_down(root,L,R);
        return (get_sum(lchild,L,mid,l,r) + get_sum(rchild,mid + 1,R,l,r)) % p;
    }
    return 0;
}
int query(int x,int y){
    int ans = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])
            swap(x,y);
        ans = (ans + get_sum(1,1,n,dfn[top[x]],dfn[x])) % p;
        x = fa[top[x]];
    }
    return (ans + get_sum(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]))) % p;
}
signed main(){
    scanf("%lld%lld%lld%lld", &n ,&m, &r, &p);
    for(int i = 1;i <= n;i++)
        scanf("%lld", &a[i]);
    for(int i = 1;i < n;i++){
        int u,v;
        scanf("%lld%lld", &u, &v);
        add_egde(u,v);
        add_egde(v,u);
    }
    dfs1(r,0);
    dfs2(r,0);
    build(1,1,n);
    for(int i = 1;i <= m;i++){
        int op,x,y,z;
        scanf("%lld", &op);
        if(op == 1){
            scanf("%lld%lld%lld", &x, &y, &z);
            update2(x,y,z);
        }
        else if(op == 2){
            scanf("%lld%lld", &x, &y);
            printf("%lld\n",query(x,y));
        }
        else if(op == 3){
            scanf("%lld%lld", &x, &y);
            update1(1,1,n,dfn[x],dfn[x] + siz[x] - 1,y);
        }
        else{
            scanf("%lld", &x);
            printf("%lld\n",get_sum(1,1,n,dfn[x],dfn[x] + siz[x] - 1) % p);
        }
    }
}