样例过 1-10TLE 11AC 玄关求调

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005
int n,m,r,p,cnt;
int fa[N],top[N],hson[N],siz[N],dep[N],id[N],a[N],w[N],f[N * 4],lazy[N * 4];
vector<int>e[N * 2];
int read(){
    int a;
    scanf("%lld",&a);
    return a;
}
void dfs1(int k,int f){
    siz[k] = 1;
    dep[k] = dep[f] + 1;
    fa[k] = f;
    for(int i = 0;i < e[k].size();i++){
        int v = e[k][i];
        if(v == f) continue;
        dfs1(v,k);
        siz[k] += siz[v];
        if(siz[hson[k]] < siz[v]){
            hson[k] = v;
        }
    }
    return;
}
void dfs2(int k,int t){
    top[k] = t;
    id[k] = ++cnt;
    w[cnt] = a[k];
    if(hson[k])
        dfs2(hson[k],t);
    for(int i = 0;i < e[k].size();i++){
        int v = e[k][i];
        if(v == hson[k] || v == fa[k]) continue;
        dfs2(v,v);
    }
    return;
}
void build(int k,int l,int r){
    if(l == r){
        f[k] = w[l];
        return;
    }
    int mid = (l + r) / 2;
    build(k * 2,l,mid);
    build(k * 2 + 1,mid + 1,r);
    f[k] = f[k * 2] + f[k * 2 + 1];
}
void change(int k,int l,int r,int v){
    lazy[k] = (lazy[k] + v) % p;
    f[k] = (f[k] + v * (r - l + 1) % p) % p;
    return;
}
void spread(int k,int l,int r){
    if(!lazy[k]) return;
    int mid = (l + r) / 2;
    change(k * 2,l,mid,lazy[k]);
    change(k * 2 + 1,mid + 1,r,lazy[k]);
    lazy[k] = 0;
}
void add(int k,int l,int r,int x,int y,int v){
    if(x <= l && r <= y){
        lazy[k] = (v + lazy[k]) % p;
        f[k] = (f[k] + ((r - l + 1) * v) % p) % p;
        return;
    }
    else{
        spread(k,l,r);
        int mid = (l + r) / 2;
        if(x <= mid) add(k * 2,l,mid,x,y,v);
        if(y > mid) add(k * 2 + 1,mid + 1,r,x,y,v);
        f[k] = (f[k * 2] + f[k * 2 + 1]) % p;
    }
}
int query(int k,int l,int r,int x,int y){
    if(x <= l && r <= y){
        return f[k];
    }
    int mid = (l + r) / 2,ans = 0;
    spread(k,l,r);
    if(x <= mid) ans = (ans + query(k * 2,l,mid,x,y)) % p;
    if(y > mid) ans = (ans + query(k * 2 + 1,mid + 1,r,x,y)) % p;
    return ans;
}
int lca(int x,int y,int v){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])
            swap(x,y);
        add(1,1,n,id[top[x]],id[x],v);
        x = fa[top[x]];

    }
    if(dep[x] > dep[y]) swap(x,y);
    add(1,1,n,id[x],id[y],v);
}
int ask1(int k,int l,int r,int x,int y){
    int ans = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])
            swap(x,y);
        ans = (ans + query(1,1,n,id[top[x]],id[x])) % p;
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    ans = (ans + query(1,1,n,id[x],id[y])) % p;
    return ans;
}
signed main(){
    n = read(),m = read(),r = read(),p = read();
    for(int i = 1;i <= n;i++)
        a[i] = read() % p;
    for(int i = 1;i <= n - 1;i++){
        int u,v;
        u = read();
        v = read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(r,0);
    dfs2(r,0);
    build(1,1,n);
    for(int i = 1;i <= m;i++){
        int op;
        op = read();
        if(op == 1){
            int x,y,z;
            x = read(),y = read(),z = read() % p;
            lca(x,y,z);
        } 
        if(op == 2){
            int x,y,z;
            x = read(),y = read();
            printf("%lld\n",ask1(1,1,n,x,y));
        }
        if(op == 3){
            int x,z;
            x = read(),z = read();
            add(1,1,n,id[x],id[x] + siz[x] - 1,z);
        }
        if(op == 4){
            int x;
            x = read();
            printf("%lld\n",query(1,1,n,id[x],id[x] + siz[x] - 1));
        }
    }

    return 0;
} 
/*
8 10 2 448348
458 718 447 857 633 264 238 944 
1 2
2 3
3 4
6 2
1 5
5 7
8 6
3 7 611
4 6
3 1 267
3 2 111
1 6 3 153
3 7 673
4 8
2 6 1
4 7
3 4 228

*/