树剖求助!37pts

#include<bits/stdc++.h>
#define int long long
#define lc(p) (p<<1)
#define rc(p) (p<<1|1) 
using namespace std;
using ll=long long;
const int N=1e6+7;
int n,m,r,mod;
struct node{
    int to,next;
}edge[N<<1];
int head[N<<1],cnt;
void init(){
    for(int i=0;i<=2*N;i++){
        edge[i].next=-1;
        head[i]=-1;
    }
}
void add_edge(int u,int v){
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
    cnt++;
}
int w[N],wn[N];
int tree[N<<2];
int tag[N<<2];
void push_up(int p){
    tree[p]=(tree[lc(p)]+tree[rc(p)])%mod;
}
void add_tag(int p,int pl,int pr,int d){
    tag[p]+=d;
    tree[p]+=(pr-pl+1)*d;
    tree[p]%=mod; 
}
void build(int p,int pl,int pr){
    if(pl==pr){
        tree[p]=wn[pl]%mod;
        return ;
    }
    int mid=pl+pr>>1;
    build(lc(p),pl,mid);
    build(rc(p),mid+1,pr);
    push_up(p);
}
void push_down(int p,int pl,int pr){
    if(tag[p]){
        int mid=pl+pr>>1;
        add_tag(lc(p),pl,mid,tag[p]);
        add_tag(rc(p),mid+1,pr,tag[p]);
        tag[p]=0;
    }
}
void update(int L,int R,int p,int pl,int pr,int d){
    if(L<=pl&&pr<=R){
        add_tag(p,pl,pr,d);
        return ;
    }
    push_down(p,pl,pr);
    int mid=pl+pr>>1;
    if(L<=mid) update(L,R,lc(p),pl,mid,d);
    if(R>mid) update(L,R,rc(p),mid+1,pr,d);
    push_up(p);
}
int query(int L,int R,int p,int pl,int pr){
    if(L<=pl&&pr<=R){
        return tree[p]%=mod;
    }
    push_down(p,pl,pr);
    int mid=pl+pr>>1;
    int res=0;
    if(L<=mid) res+=query(L,R,lc(p),pl,mid);
    if(R>mid) res+=query(L,R,rc(p),mid+1,pr);
    return res;
}
int son[N],id[N],fa[N];
int deep[N],siz[N],top[N];
int num;
void dfs1(int x,int father){
    deep[x]=deep[father]+1;
    fa[x]=father;
    siz[x]=1;
    for(int i=head[x];~i;i=edge[i].next){
        int y=edge[i].to;
        if(y==father) continue;
        fa[y]=x;
        dfs1(y,x);
        siz[x]+=siz[y];
        if(!son[x]||siz[son[x]]<siz[y]){
            son[x]=y;
        }
    }
} 
void dfs2(int x,int topx){
    num++;
    id[x]=num;
    wn[num]=w[x];
    top[x]=topx;
    if(!son[x]) return ;
    dfs2(son[x],topx);
    for(int i=head[x];~i;i=edge[i].next){
        int y=edge[i].to;
        if(y!=fa[x]&&y!=son[x]) dfs2(y,y);
    }
}
void update_range(int x,int y,int z){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]){
            swap(x,y);
        }
        update(id[top[x]],id[x],1,1,n,z);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    update(id[x],id[y],1,1,n,z);
}
int query_range(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]){
            swap(x,y);
        }
        ans+=query(id[top[x]],id[x],1,1,n);
        ans%=mod;
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    ans+=query(id[x],id[y],1,1,n);
    return ans;
}
void Update(int x,int k){
    update(id[x],id[x]+siz[x]-1,1,1,n,k);
}
int Query(int x){
    return query(id[x],id[x]+siz[x]-1,1,1,n)%mod;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();
    cin>>n>>m>>r>>mod;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs1(r,0);
    dfs2(r,r);
    build(1,1,n);
    while(m--){
        int op,x,y,z;
        cin>>op;
        if(op==1){
            cin>>x>>y>>z;
            update_range(x,y,z);
        }
        else if(op==2){
            cin>>x>>y;
            cout<<query_range(x,y)<<"\n";
        }
        else if(op==3){
            cin>>x>>y;
            Update(x,y);
        }
        else{
            cin>>x;
            cout<<Query(x)<<"\n";
        }
    }
    return 0;
}