10tps,求调

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,m,r,P,tot;
struct dot{
    int data,top,son,fa,map,dep,siz;
    vector<int>edge;
};
dot e[N];
int mp[N];
void dfs1(int u,int father){
    e[u].dep=e[father].dep+1;
    e[u].fa=father;
    e[u].siz=1;
    for(int v:e[u].edge){
        if(v==father) continue;
        dfs1(v,u);
        e[u].siz+=e[v].siz;
        if(e[e[u].son].siz<e[v].siz)
            e[u].son=v;
    }
}
void dfs2(int u,int t){
    e[u].top=t;
    e[u].map=++tot;
    mp[tot]=u;
    if(!e[u].son) return;
    dfs2(e[u].son,t);
    for(int v:e[u].edge)
        if(v!=e[u].fa&&v!=e[u].son)
            dfs2(v,v);
}
struct line{
    int l,r;
    long long sum,add;
};
line tree[N<<2];
void build(int k,int l,int r){
    tree[k].l=l;tree[k].r=r;
    if(l==r){
        tree[k].sum=e[mp[k]].data%P;
        return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tree[k].sum=(tree[k<<1].sum+tree[k<<1|1].sum)%P;
}
void pushdown(int k){
    if(tree[k].add){
        tree[k<<1].add=(tree[k<<1].add+tree[k].add)%P;
        tree[k<<1|1].add=(tree[k<<1|1].add+tree[k].add)%P;
        tree[k<<1].sum=(tree[k<<1].sum+tree[k].add*(tree[k<<1].r-tree[k<<1].l+1))%P;
        tree[k<<1|1].sum=(tree[k<<1|1].sum+tree[k].add*(tree[k<<1|1].r-tree[k<<1|1].l+1))%P;
        tree[k].add=0;
    }
}
void change(int k,int l,int r,long long add){
    if(tree[k].l>=l&&tree[k].r<=r){
        tree[k].sum=(tree[k].sum+add*(tree[k].r-tree[k].l+1))%P;
        tree[k].add=(tree[k].add+add)%P;
        return;
    }
    pushdown(k);
    int mid=tree[k].l+tree[k].r>>1;
    if(l<=mid) change(k<<1,l,r,add);
    if(r>mid) change(k<<1|1,l,r,add);
    tree[k].sum=(tree[k<<1].sum+tree[k<<1|1].sum)%P;
}
long long ask(int k,int l,int r){
    if(tree[k].l>=l&&tree[k].r<=r)
        return tree[k].sum;
    pushdown(k);
    int mid=tree[k].l+tree[k].r>>1;
    long long res=0;
    if(l<=mid) res=(res+ask(k<<1,l,r))%P;
    if(r>mid) res=(res+ask(k<<1|1,l,r))%P;
    return res;
}
void changetree(int u,int v,long long add){
    while(e[u].top!=e[v].top){
        if(e[e[u].top].dep<e[e[v].top].dep) swap(u,v);
        change(1,e[e[u].top].map,e[u].map,add);
        u=e[e[u].top].fa;
    }
    if(e[u].dep>e[v].dep) swap(u,v);
    change(1,e[u].map,e[v].map,add);
}
long long asktree(int u,int v){
    long long res=0;
    while(e[u].top!=e[v].top){
        if(e[e[u].top].dep<e[e[v].top].dep) swap(u,v);
        res=(res+ask(1,e[e[u].top].map,e[u].map))%P;
        u=e[e[u].top].fa;
    }
    if(e[u].dep>e[v].dep) swap(u,v);
    res=(res+ask(1,e[u].map,e[v].map))%P;
    return res;
}
long long askson(int u){
    return ask(1,e[u].map,e[u].map+e[u].siz-1);
}
void changeson(int u,long long add){
    change(1,e[u].map,e[u].map+e[u].siz-1,add);
}
int main(){
    scanf("%d%d%d%d",&n,&m,&r,&P);
    for(int i=1;i<=n;i++)
        scanf("%d",&e[i].data);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].edge.push_back(v);
        e[v].edge.push_back(u);
    }
    dfs1(r,0);
    dfs2(r,r);
    build(1,1,n);
    while(m--){
        int opt;
        scanf("%d",&opt);
        if(opt==1){
            int u,v;
            long long value;
            scanf("%d%d%lld",&u,&v,&value);
            changetree(u,v,value);
        }
        if(opt==2){
            int u,v;
            scanf("%d%d",&u,&v);
            printf("%lld\n",asktree(u,v));
        }
        if(opt==3){
            int u;
            long long value;
            scanf("%d%lld",&u,&value);
            changeson(u,value);
        }
        if(opt==4){
            int u;
            scanf("%d",&u);
            printf("%lld\n",askson(u));
        }
    }
    return 0;
}