37分求助

#include<bits/stdc++.h>
//#include<vector>
using namespace std;
const int N=1e5+5;
vector<int>to[N];
int size[N],son[N],fa[N],dep[N],sum[N*4],a[N];
int dfn[N],rev[N],top[N],tag[N];
int cnt,n,p;
void dfsson(int rt){
    size[rt]=1;
    dep[rt]=dep[fa[rt]]+1;
    for(int i=0;i<(int)to[rt].size();i++)
    {
        int v=to[rt][i];
        if(v==fa[rt])continue;
        fa[v]=rt;
        dfsson(v);
        size[rt]+=size[v];
        if(size[v]>size[son[rt]])
            son[rt]=v;
    }
}
void dfs(int rt){
    dfn[rt]=++cnt;
    rev[cnt]=rt;
    if(son[rt])
    {
        top[son[rt]]=top[rt];
        dfs(son[rt]);
    }
    for(int i=0;i<(int)to[rt].size();i++)
    {
        int v=to[rt][i];
        if(v!=fa[rt]&&v!=son[rt])
        {
            top[v]=v;
            dfs(v);
        }

    }
}
void push_down(int rt,int l,int r){
    int mid=(l+r)>>1; 
    tag[rt*2]+=tag[rt];
    tag[rt*2+1]+=tag[rt];
    sum[rt*2]+=(mid-l+1)*tag[rt];sum[rt*2]%=p;
    sum[rt*2+1]+=(r-mid)*tag[rt];sum[rt*2+1]%=p;
    tag[rt]=0;
}
void modify(int rt,int l,int r,int x,int y,int v){
    if(x<=l&&r<=y)
    {
        tag[rt]+=v;
        sum[rt]+=v*(r-l+1);
        sum[rt]%=p;
        return ;
    }
    if(r<x||y<l) return ;
    int mid=(l+r)>>1;
    push_down(rt,l,r);
    modify(rt*2,l,mid,x,y,v);
    modify(rt*2+1,mid+1,r,x,y,v);
    sum[rt]=sum[rt*2]+sum[rt*2+1];
    sum[rt]%=p;
}
int  query(int rt,int l,int r,int x,int y){
    if(x<=l&&r<=y)return sum[rt]%=p;
    if(r<x||y<l) return 0;
    int result=0;
    int mid=(l+r)>>1;
    push_down(rt,l,r);
    result+=query(rt*2,l,mid,x,y);
    result+=query(rt*2+1,mid+1,r,x,y);
    return result;
}
void modify_edge(int x,int y,int v){
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        modify(1,1,n,dfn[top[x]],dfn[x],v);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    modify(1,1,n,dfn[x],dfn[y],v);
}
int  query_edge(int x,int y){
    int result=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        result+=query(1,1,n,dfn[top[x]],dfn[x]);
        result%=p;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    result+=query(1,1,n,dfn[x],dfn[y]);
    result%=p;
    return result;
}
void modify_tree(int x,int v){
    modify(1,1,n,dfn[x],dfn[x]+size[x]-1,v);
}
int  query_tree(int x){
//  cout << dfn[x] << ' ' << dfn[x] + size[x] - 1 << "aaa";
    return query(1,1,n,dfn[x],dfn[x]+size[x]-1);
}
void build(int rt,int l,int r){
    if(l==r)
    {
        sum[rt]=a[rev[l]];
        sum[rt]%=p;
//      cout << l << ' ' << rev[l] << ' ' << a[rev[l]] << endl; 
        return ;
    }
    int mid=(l+r)>>1;
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    sum[rt]=sum[rt*2]+sum[rt*2+1];
    sum[rt]%=p;
}
int main()
{
    int m,root;
    cin>>n>>m>>root>>p;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i]%=p;
    } 
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        to[u].push_back(v);
        to[v].push_back(u);
    }
    top[root]=root;
    dfsson(root);
    dfs(root);
    build(1,1,n);
    while(m--)
    {
        int sign,x,y,z;
        scanf("%d",&sign);
        if(sign==1)
        {
            scanf("%d %d %d",&x,&y,&z);
            modify_edge(x,y,z);
        }
        if(sign==2)
        {
            scanf("%d %d",&x,&y);
            cout<<query_edge(x,y)<<endl;
        }
        if(sign==3)
        {
            scanf("%d %d",&x,&z);
            modify_tree(x,z);
        }
        if(sign==4)
        {
            scanf("%d",&x);
            cout<<query_tree(x)<<endl;
        }
    }
    return 0;
}