树刨27分求调 QAQ

#include<bits/stdc++.h>
#define maxn 5000010
#define lc k<<1
#define rc k<<1|1
using namespace std;
struct node1{
    int l,r,w,len,lzy;
}tree[maxn];
int a[maxn];
//-----线段树
struct node2{
    int to,nxt;
}edge[maxn];
int h[maxn],cnt0;//w[]初始点权，wt[]赋值后点权
//-----链式前向星
int son[maxn],fa[maxn],deep[maxn],siz[maxn],idx[maxn],top[maxn],wt[maxn],cnt;
//-----树链刨分
//son是当前节点的重儿子，fa当前节点父节点，deep当前节点深度，cnt二次映射编号，siz当前节点子树的大小，w当前结点的原始值，idx当前节点的新编号，wt当前节点的现值在原始值的下标，top当前链的链首
long long res;//存结果
int n,m,MOD,root;
void add(int u,int v){
    edge[++cnt0].to=v;
    edge[cnt0].nxt=h[u];
    h[u]=cnt0;
}//链式前向星存图
void dfs1(int u,int f){//u是当前节点，f是父节点
    deep[u]=deep[f]+1;
    fa[u]=f;
    siz[u]=1;//初始为1，后续赋值
    for(int i=h[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==f){
            continue;
        }
        dfs1(v,u);//递归向下寻找子节点的子树
        siz[u]+=siz[v];//子节点的子树大小合并
        if(siz[v]>siz[son[u]]){//打擂寻找重儿子
            son[u]=v;
        }
    }
}
void dfs2(int u,int tp){//tp当前链的链首
    idx[u]=++cnt;
    wt[cnt]=u;
    top[u]=tp;
    if(!son[u]){//如果不是重儿子就返回
        return; 
    }
    dfs2(son[u],tp);//是重儿子沿着链继续排序
    for(int i=h[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        if(idx[v])continue;//如果排序过就跳过
        dfs2(v,v);//拍到非重儿子的时候仍需排序
    }
    return ;
}
void update(int k){
    tree[k].w=(tree[lc].w+tree[rc].w+MOD)%MOD;
}
void pushdown(int k){
    if(!tree[k].lzy)return;
    tree[lc].w=(tree[lc].w+tree[rc].len*tree[k].lzy)%MOD;
    tree[rc].w=(tree[rc].w+tree[rc].len*tree[k].lzy)%MOD;
    tree[lc].lzy=(tree[lc].lzy+tree[k].lzy)%MOD;
    tree[rc].lzy=(tree[rc].lzy+tree[k].lzy)%MOD;
    tree[k].lzy=0;
}
void build(int k,int l,int r){
    tree[k].l=l;
    tree[k].r=r;
    tree[k].len=r-l+1;
    if(l==r){
        tree[k].w=a[wt[l]];
        return ;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    update(k);  
}
void Range_update(int k,int l,int r,int v){
    if(l<=tree[k].l && tree[k].r<=r){
        tree[k].w+=tree[k].len*v;
        tree[k].lzy+=v;
        return ;
    }
    pushdown(k);
    int mid=(tree[k].l+tree[k].r)>>1;
    if(l<=mid) Range_update(lc,l,r,v);
    if(r>mid)  Range_update(rc,l,r,v);
    update(k);
}
int Range_qry(int k,int l,int r){
    int ans=0;
    if(l<=tree[k].l && tree[k].r<=r){
        return tree[k].w;
    }
    pushdown(k);
    int mid=(tree[k].l+tree[k].r)>>1;
    if(l<=mid) ans=(ans+Range_qry(lc,l,r))%MOD;
    if(r>mid)  ans=(ans+Range_qry(rc,l,r))%MOD;
    return ans;
}
int Range_tree_qry(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        ans=(ans+Range_qry(1,idx[top[x]],idx[x]))%MOD;
        x=fa[top[x]];
    }
    if(deep[x]>deep[y])swap(x,y);
    ans=(ans+Range_qry(1,idx[x],idx[y]))%MOD;
    return ans;
}
void Range_tree_update(int x,int y,int v){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        Range_update(1,idx[top[x]],idx[x],v);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y])swap(x,y);
    Range_update(1,idx[x],idx[y],v);
}
int main(){
    memset(h,-1,sizeof(h));
    cin>>n>>m>>root>>MOD;
    // cout<<n<<m<<root<<MOD
    for(int i=1;i<=n;i++){
        cin>>a[i];
        // cout<<a[i];
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
        // cout<<"a ";
    }
    deep[0]=1;
    // cout<<"sda";
    dfs1(root,0);
    // cout<<"sda";
    dfs2(root,root);
    build(1,1,n);
    while(m--){
        int opt,x,y,z;
        cin>>opt;
        if(opt==1){
            // cout<<"sda";
            cin>>x>>y>>z;
            z=z%MOD;
            Range_tree_update(x,y,z);
        }else if(opt==2){
            // cout<<"sda";
            cin>>x>>y;
            cout<<Range_tree_qry(x,y)<<"\n";
        }else if(opt==3){
            // cout<<"sda";
            cin>>x>>z;
            Range_update(1,idx[x],idx[x]+siz[x]-1,z%MOD);
        }else{
            // cout<<"sda";
            cin>>x;
            cout<<Range_qry(1,idx[x],idx[x]+siz[x]-1)<<"\n";
        }
    }
    return 0;
}