37pts 求助

# include <iostream>
# include <cmath>
# include <cstring>
# include <string>
# include <algorithm>
# include <stack>
# include <queue>
# include <vector>
# include <set>
# include <map>
using namespace std;

int n,m,r,p,u,v;

int head[1000005],num=0;
struct pnode {
    int to,next;
}edge[1000005];
void add(int u,int v){
    edge[++num].next=head[u];
    edge[num].to=v;
    head[u]=num;
}

int dep[1000005],fa[1000005],siz[1000005];
int wson[1000005];
void dfs1(int father,int x){
    dep[x]=dep[father]+1;
    fa[x]=father;
    siz[x]=1;
    int mson=-1;
    for(int i=head[x];i;i=edge[i].next){
        if (father==edge[i].to) continue;
        dfs1(x,edge[i].to);
        siz[x]+=siz[edge[i].to];
        if (siz[edge[i].to]>mson) {
            wson[x]=edge[i].to;
            mson=siz[edge[i].to];
        }
    }
}

int cnt=0;
int id[1000005],top[1000005];
int w[1000005],wt[1000005];
void dfs2(int x,int topf){
    id[x]=++cnt;
    wt[cnt]=w[x];
    top[x]=topf;
    if (wson[x]==0) return;
    dfs2(wson[x],topf);
    for (int i=head[x];i;i=edge[i].next){
        if (edge[i].to==fa[x]||edge[i].to==wson[x]) continue;
        dfs2(edge[i].to,edge[i].to);
    }
}

struct node {
    long long val,mark;
}tree[1000005];
void build (int st,int ed,int root){
    if (st==ed){
        tree[root].val=wt[st];
        tree[root].val%=p;
        return ;
    }
    int mid=(st+ed)/2;
    build(st,mid,root*2);
    build(mid+1,ed,root*2+1);
    tree[root].val=(tree[root*2].val+tree[root*2+1].val)%p;
}
void pushdown (int root,int l,int r){
    if (tree[root].mark!=0){
        int mid=(l+r)/2;
        tree[root*2].mark+=tree[root].mark;
        tree[root*2+1].mark+=tree[root].mark;
        tree[root*2].val+=tree[root].mark*(mid-l+1);
        tree[root*2+1].val+=tree[root].mark*(r-mid);
        tree[root*2].val%=p;
        tree[root*2+1].val%=p;
        tree[root].mark=0;
    }
}
long long quary (int root,int st,int ed,int qst,int qed){
    if (qed<st||ed<qst) return 0;
    if (qst<=st&&ed<=qed) return tree[root].val%p;
    pushdown(root,st,ed);
    int mid=(st+ed)/2;
    long long ans=0;
    if (qst<=mid) ans+=quary(root*2,st,mid,qst,qed);
    if (qed>mid) ans+=quary(root*2+1,mid+1,ed,qst,qed);
    return ans;
}
void update (int root,int st,int ed,int qst,int qed,long long val){
    if (qed<st||ed<qst) return ;
    if (qst<=st&&ed<=qed) {
        tree[root].mark+=val;
        tree[root].val+=val*(ed-st+1);
        return ;
    }
    pushdown(root,st,ed);
    int mid=(st+ed)/2;
    if (qst<=mid) update (root*2,st,mid,qst,qed,val);
    if (qed>mid) update (root*2+1,mid+1,ed,qst,qed,val);
    tree[root].val=(tree[root*2].val+tree[root*2+1].val)%p;
}

void update_range (int x,int y,int k){
    k%=p;
    while (top[x]!=top[y]){
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        update(1,1,n,id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    update(1,1,n,id[x],id[y],k);
    return ;
}
int ask_range (int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans=(ans+quary(1,1,n,id[top[x]],id[x]))%p;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    return (ans+quary(1,1,n,id[x],id[y]))%p;
}
int ask_son (int x){
    return quary(1,1,n,id[x],id[x]+siz[x]-1);
}
void update_son (int x,int k){
    update(1,1,n,id[x],id[x]+siz[x]-1,k);
}
int main(){
    //freopen("P3384_4.in","r",stdin);
    //freopen("P3384.out","w",stdout);
    ios::sync_with_stdio (false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >>n>>m>>r>>p;
    for (int i=1;i<=n;i++)
        cin >>w[i];
    for (int i=1;i<n;i++){
        cin >>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs1(0,r);
    dfs2(r,r);
    build(1,n,1);
    for (int i=1;i<=m;i++){
        int opt,x,y,z;
        cin >>opt;
        if (opt==1){
            cin >>x>>y>>z;
            update_range(x,y,z);
        }
        if (opt==2){
            cin >>x>>y;
            cout <<ask_range(x,y)<<endl;
        }
        if (opt==3){
            cin >>x>>y;
            update_son(x,y);
        }
        if (opt==4){
            cin >>x;
            cout <<ask_son(x)<<endl;
        }
    }
    return 0;
}