TLE 10pts萌新求条

#include<bits/stdc++.h>
using namespace std;
int n,m,r,P;
int p[200005],siz[200005],d[200005],son[200005],top[200005],id[200005],cnt,val[200005],f[200005];
vector<int> c[200005],tr[200005];
int L[800005],R[800005];
long long sum[800005],lazy[800005];
void build(int l, int r, int x){
    L[x] = l, R[x] = r, lazy[x] = 0;
    if (l == r) {
        sum[x]=val[l]%P;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, x * 2);
    build(mid + 1, r, x * 2 + 1);
    sum[x] = (sum[x*2]+sum[x*2+1])%P;
    return;
}
int Len(int x){
    return R[x] - L[x] + 1;
}
void pushdown(int x){
    if (lazy[x]){
        lazy[x * 2]=(lazy[x*2]+lazy[x])%P;
        lazy[x * 2 + 1]=(lazy[x*2+1]+lazy[x])%P;
        sum[x * 2]=(sum[x*2]+lazy[x] * Len(x * 2))%P;
        sum[x * 2 + 1]=(sum[x*2+1]+lazy[x] * Len(x * 2+1))%P;
        lazy[x] = 0;
    }
    return;
}
void update(int l, int r, int x, long long k){ 
    if (l <= L[x] && R[x] <= r){
        lazy[x]=(lazy[x]+k)%P;
        sum[x]=(sum[x]+k *Len(x))%P;
        return;
    } 
    pushdown(x);
    int mid = (L[x] + R[x]) / 2;
    if (l <= mid) update(l, r, x * 2, k);
    if (r > mid) update(l, r, x * 2 + 1, k);
    sum[x] =(sum[x * 2] + sum[x * 2 + 1])%P; 
}
long long query(int l, int r, int x){
    if (l <= L[x] && R[x] <= r){
        return sum[x];
    }
    pushdown(x);
    long long ret = 0; int mid = (L[x] + R[x]) / 2;
    if (l <= mid) ret += query(l, r, x * 2);
    if (r > mid) ret += query(l, r, x * 2 + 1);
    return ret%P;
}
void dfs1(int nowp,int dep){
    siz[nowp]=1;
    d[nowp]=dep;
    for(int i=0;i<c[nowp].size();++i){
        if(c[nowp][i]!=f[nowp]){
            f[c[nowp][i]]=nowp;
            dfs1(c[nowp][i],dep+1);
            tr[nowp].push_back(c[nowp][i]);
            siz[nowp]+=siz[c[nowp][i]];
            if(siz[c[nowp][i]]>siz[son[nowp]]){
                son[nowp]=c[nowp][i];
            }
        }
    } 
    if(siz[nowp]==1) son[nowp]=-1;
}
void dfs2(int nowp,int topx){
    id[nowp]=++cnt;
    val[cnt]=p[nowp];
    top[cnt]=topx;
    if(son[nowp]==-1) return;
    dfs2(son[nowp],topx);
    for(int i=0;i<tr[nowp].size();++i){
        if(tr[nowp][i]!=son[nowp]){
            dfs2(tr[nowp][i],tr[nowp][i]);
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>r>>P;
    for(int i=1;i<=n;++i) cin>>p[i];
    for(int i=1;i<n;++i){
        int a,b;
        cin>>a>>b;
        c[a].push_back(b);
        c[b].push_back(a);
    }
    f[r]=0;
    dfs1(r,0);
    dfs2(r,r);
    build(1,n,1);
    while(m--){
        int op,x,y,z;
        cin>>op;
        if(op==1){
            cin>>x>>y>>z;
            while(top[id[x]]!=top[id[y]]){
                if(d[top[id[x]]]<d[top[id[y]]]) swap(x,y);
                update(id[top[id[x]]],id[x],1,z%P);
                x=f[top[x]];
            }
            if(d[x]>d[y]) swap(x,y);
            update(id[x],id[y],1,z%P);
        }else if(op==2){
            cin>>x>>y;
            long long ret=0;
            while(top[id[x]]!=top[id[y]]){
                if(d[top[id[x]]]<d[top[id[y]]]) swap(x,y);
                ret+=query(id[top[id[x]]],id[x],1);
                x=f[top[id[x]]];
            }
            if(d[x]>d[y]) swap(x,y);
            ret+=query(id[x],id[y],1);  
            cout<<ret%P<<'\n';
        }else if(op==3){
            cin>>x>>z;
            update(id[x],id[x]+siz[id[x]]-1,1,z%P);
        }else{
            cin>>x;
            cout<<query(id[x],id[x]+siz[id[x]]-1,1)%P<<'\n';
        }
    }
    return 0;
}