63pts求调

#include<bits/stdc++.h>
#define ll long long
#define N (int)1e5+5
using namespace std;
int n,m,root,mod,cnt,tot,a[N],head[N],dep[N],sz[N],son[N],id[N],top[N],fat[N];
ll na[N],tr[N<<2],la[N<<2];
struct Edge{
    int u,v,nxt;
}e[N<<1];
inline void add(int u,int v){
    e[++cnt]=Edge{u,v,head[u]};
    head[u]=cnt;
}
void dfs1(int u,int fa){
    dep[u]=dep[fa]+1;sz[u]=1;fat[u]=fa;
    for(int i=head[u];i;i=e[i].nxt){
        if(e[i].v==fa) continue;
        dfs1(e[i].v,u);
        sz[u]+=sz[e[i].v];
        if(sz[e[i].v]>sz[son[u]]) son[u]=e[i].v;
    }
}
void dfs2(int u,int fa){
    id[u]=++tot,na[tot]=a[u];
    if(son[u]) top[son[u]]=top[u],dfs2(son[u],u);
    for(int i=head[u];i;i=e[i].nxt){
        if(e[i].v==fa||e[i].v==son[u]) continue;
        top[e[i].v]=e[i].v;
        dfs2(e[i].v,u);
    }
}
void pushup(int p){
    tr[p]=tr[p<<1]+tr[p<<1|1];
}
void build(int l,int r,int p){
    if(l==r){
        tr[p]=na[l];
        return ;
    }
    int m=(l+r)>>1;
    build(l,m,p<<1);build(m+1,r,p<<1|1);
    pushup(p);
}
void pushdown(int s,int t,int p){
    int m=s+t>>1;
    if(la[p]) tr[p<<1]+=la[p]*(m-s+1),tr[p<<1|1]+=la[p]*(t-m),la[p<<1]+=la[p],la[p<<1|1]+=la[p];
    la[p]=0;
}
void update(int l,int r,int s,int t,int c,int p){
    if(l<=s&&t<=r){
        tr[p]+=c*(t-s+1);
        tr[p]%=mod;
        la[p]+=c;
        la[p]%=mod;
        return ;
    }
    pushdown(s,t,p);
    int m=(s+t)>>1;
    if(l<=m) update(l,r,s,m,c,p<<1);
    if(r>m) update(l,r,m+1,t,c,p<<1|1);
    pushup(p);
}
ll query(int l,int r,int s,int t,int p){
    if(l<=s&&t<=r) return tr[p];
    pushdown(s,t,p);
    ll m=(s+t)>>1,v=0;
    if(l<=m) v=query(l,r,s,m,p<<1)%mod;
    if(r>m) v+=query(l,r,m+1,t,p<<1|1)%mod;
    return v%mod;
}
void update_tree(int u,int c){
    update(id[u],id[u]+sz[u]-1,1,n,c,1);
}
void update_path(int u,int v,int c){
    while(top[u]^top[v]){
        if(dep[top[u]]<dep[top[v]]) u^=v^=u^=v;
        update(id[top[u]],id[u],1,n,c,1);
        u=fat[top[u]];
    }
    if(dep[u]<dep[v]) u^=v^=u^=v;
    update(id[v],id[u],1,n,c,1);
}
ll query_path(int u,int v){
    ll ans=0;
    while(top[u]^top[v]){
        if(dep[top[u]]<dep[top[v]]) u^=v^=u^=v;
        ans+=query(id[top[u]],id[u],1,n,1);
        ans%=mod;
        u=fat[top[u]];
    }
    if(dep[u]<dep[v]) u^=v^=u^=v;
    return (query(id[v],id[u],1,n,1)+ans)%mod;
}
ll query_tree(int u){
    return query(id[u],id[u]+sz[u]-1,1,n,1);
}
int main(){
    scanf("%d%d%d%d",&n,&m,&root,&mod);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),add(u,v),add(v,u);
    top[root]=root;
    dfs1(root,0);
    dfs2(root,0);
    build(1,n,1);
    while(m--){
        int op,x,y,z;
        scanf("%d%d",&op,&x);
        if(op==1){
            scanf("%d%d",&y,&z);
            update_path(x,y,z);
        }
        else if(op==2){
            scanf("%d",&y);
            printf("%d %d %d?\n",op,x,y);
            printf("%lld\n",query_path(x,y));
        }
        else if(op==3){
            scanf("%d",&z);
            update_tree(x,z);
        }
        else printf("%lld\n",query_tree(x));
    }
    return 0;
}

目前已知的问题是在操作2时，top[u]=top[v]=0了