73pts求调

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
typedef struct node{
    int to,w,next;
}node;
node edge[MAXN];
int head[MAXN],dfn[MAXN],fa[MAXN],dep[MAXN],sz[MAXN],wc[MAXN],topp[MAXN],rdfn[MAXN],a[MAXN];
long long w[MAXN << 2],tag[MAXN << 2];
int cnt,n,r,p,m,vistime;
void add_edge(int u,int v,int w){
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
    return;
}
void init(){
    memset(head,-1,sizeof(head));
    return;
}
void dfs_rechain(int u,int f){
    fa[u] = f;
    sz[u] = 1;
    dep[u] = dep[f] + 1;
    for(int i = head[u]; i ^ -1; i = edge[i].next){
        int v = edge[i].to;
        if(!(v ^ f)){
            continue;
        }
        dfs_rechain(v,u);
        sz[u] += sz[v];
        if(sz[v] > sz[wc[u]]){
            wc[u] = v;
        }
    }
    return;
}
void dfs_dfn(int u,int top){
    topp[u] = top;
    dfn[u] = ++vistime;
    rdfn[vistime] = u;
    if(!wc[u]){
        return;
    }
    if(wc[u]){
        dfs_dfn(wc[u],top);
    }
    for(int i = head[u]; i ^ -1; i = edge[i].next){
        int v = edge[i].to;
        if(!(v ^ fa[u]) || !(v ^ wc[u])){
            continue;
        }
        dfs_dfn(v,v);
    }
    return;
}
void dfs(){
    dfs_rechain(r,0);
    dfs_dfn(r,0);
    return;
}
void pushup(int u){
    w[u] = (w[u << 1] + w[(u << 1) | 1]) % p;
    return;
}
void build(int u,int L,int R){
    if(!(L ^ R)){
        w[u] = a[rdfn[L]];
        return;
    }
    int mid = (L + R) >> 1;
    build(u << 1,L,mid);
    build((u << 1) | 1,mid + 1,R);
    pushup(u);
    return;
}
bool inRange(int L,int R,int l,int r){
    return (l <= L) && (R <= r);
}
bool outRange(int L,int R,int l,int r){
    return (L > r) || (R < l);
}
void makeTag(int u,int len,long long x){
    tag[u] += x;
    w[u] += len * x % p;
    tag[u] %= p;
    w[u] %= p;
    return;
}
void pushdown(int u,int L,int R){
    int mid = (L + R) >> 1;
    makeTag(u << 1,mid - L + 1,tag[u]);
    makeTag((u << 1) | 1,R - mid,tag[u]);
    tag[u] = 0;
    return;
}
int query(int u,int L,int R,int l,int r){
    if(inRange(L,R,l,r)){
        return w[u];
    }
    if(!outRange(L,R,l,r)){
        int mid = (L + R) >> 1;
        pushdown(u,L,R);
        return (query(u << 1,L,mid,l,r) + query((u << 1) | 1,mid + 1,R,l,r)) % p;
    }
    return 0;
}
void update(int u,int L,int R,int l,int r,long long x){
    if(inRange(L,R,l,r)){
        makeTag(u,R - L + 1,x);
        return;
    }
    if(!outRange(L,R,l,r)){
        int mid = (L + R) >> 1;
        pushdown(u,L,R);
        update(u << 1,L,mid,l,r,x);
        update((u << 1) | 1,mid + 1,R,l,r,x);
        pushup(u);
    }
    return;
}
void upd(int x,int y,int z){
    while(topp[x] ^ topp[y]){
        if(dep[topp[x]] < dep[topp[y]]){
            swap(x,y);
        }
        update(1,1,n,dfn[topp[x]],dfn[x],z);
        x = fa[topp[x]];
    }
    update(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),z);
    return;
}
int qry(int x,int y){
    long long ans = 0;
    while(topp[x] ^ topp[y]){
        if(dep[topp[x]] < dep[topp[y]]){
            swap(x,y);
        }
        ans += query(1,1,n,dfn[topp[x]],dfn[x]);
        ans %= p;
        x = fa[topp[x]];
    }
    return (ans + query(1,1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]))) % p;;
}
int main(){
    init();
    scanf("%d%d%d%d",&n,&m,&r,&p);
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
    }
    for(int i = 1; i < n; i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add_edge(u,v,0);
        add_edge(v,u,0);
    }
    dfs();
    build(1,1,n);
    for(int i = 1; i <= m; i++){
        int opt,x,y,z;
        scanf("%d",&opt);
        if(!(opt ^ 1)){
            scanf("%d%d%d",&x,&y,&z);
            upd(x,y,z);
        }
        else if(!(opt ^ 2)){
            scanf("%d%d",&x,&y);
            printf("%d\n",qry(x,y));
        }
        else if(!(opt ^ 3)){
            scanf("%d%d",&x,&y);
            update(1,1,n,dfn[x],dfn[x] + sz[x] - 1,y);
        }
        else{
            scanf("%d",&x);
            printf("%lld\n",query(1,1,n,dfn[x],dfn[x] + sz[x] - 1) % p);
        }
    }
    return 0;
}