性感代码树剖求调 37pts

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,q,s,p,a[N];
vector<int>G[N];
int fa[N],dep[N],siz[N],son[N];
int top[N],seg[N],idx,rev[N];
void dfs1(int u,int Fa){
  siz[u]=1,fa[u]=Fa,dep[u]=dep[Fa]+1;
  for(int v:G[u]) if(v!=Fa){
    dfs1(v,u),siz[u]+=siz[v];
    if(siz[v]>siz[son[u]]) son[u]=v; //heavy son
  }
}
void dfs2(int u,int Fa){
  if(son[u]){
    seg[son[u]]=++idx;
    top[son[u]]=top[u];
    rev[idx]=son[u];
    dfs2(son[u],u);
  }
  for(int v:G[u]) if(v!=Fa&&v!=son[u])
    seg[v]=++idx,top[v]=v,rev[idx]=v,dfs2(v,u);
}
int sum[N<<2],lzy[N<<2];
void pushup(int u){
  sum[u]=(sum[u*2]+sum[u*2+1])%p;
}
void pushdown(int u,int l,int r){
  int mid=l+r>>1;
  (sum[u*2]+=lzy[u]*(mid-l+1)%p)%=p;
  (sum[u*2+1]+=lzy[u]*(r-mid)%p)%=p;
  (lzy[u*2]+=lzy[u])%=p;
  (lzy[u*2+1]+=lzy[u])%=p;
  lzy[u]=0;
}
void build(int u,int l,int r){
  if(l==r) return void(sum[u]=a[rev[l]]%p);
  int mid=l+r>>1; 
  build(u*2,l,mid); 
  build(u*2+1,mid+1,r);
  pushup(u);
}
void update(int u,int l,int r,int x,int y,int k){
  if(x<=l&&r<=y) return (sum[u]+=k*(r-l+1)%p)%=p,void((lzy[u]+=k)%=p);
  int mid=l+r>>1; pushdown(u,l,r);
  if(x<=mid) update(u*2,l,mid,x,y,k);
  if(y>mid) update(u*2+1,mid+1,r,x,y,k);
  pushup(u);
}
int query(int u,int l,int r,int x,int y){
  if(x<=l&&r<=y) return sum[u];
  int mid=l+r>>1; pushdown(u,l,r); //pushup(u);
  if(y<=mid) return query(u*2,l,mid,x,y);
  if(x>mid) return query(u*2+1,mid+1,r,x,y);
  return (query(u*2,l,mid,x,y)+query(u*2+1,mid+1,r,x,y))%p;
}  
int query_chain(int u,int v){
  int ans=0;
  int fu=top[u],fv=top[v];
  while(fu!=fv){
    if(dep[fu]<dep[fv]) swap(u,v),swap(fu,fv);
    (ans+=query(1,1,n,seg[fu],seg[u]))%=p;
    u=fa[fu],fu=top[u];
  }
  if(dep[u]>dep[v]) swap(u,v);
  (ans+=query(1,1,n,seg[u],seg[v]))%=p;
  return ans;
}
void update_chain(int u,int v,int w){
  int fu=top[u],fv=top[v];
  while(fu!=fv){
    if(dep[fu]<dep[fv]) swap(u,v),swap(fu,fv);
    update(1,1,n,seg[fu],seg[u],w);
    u=fa[u],fu=top[u];
  }
  if(dep[u]>dep[v]) swap(u,v);
  update(1,1,n,seg[u],seg[v],w);
}
int query_subtree(int u){
  return query(1,1,n,seg[u],seg[u]+siz[u]-1);
}
void update_subtree(int u,int w){
  update(1,1,n,seg[u],seg[u]+siz[u]-1,w);
}
main(){
  cin.tie(0)->sync_with_stdio(0);
  cin>>n>>q>>s>>p;
  for(int i=1;i<=n;++i) cin>>a[i];
  for(int i=1,u,v;i<n;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
  dfs1(s,0),idx=seg[s]=1,rev[1]=top[s]=s,dfs2(s,0);
  build(1,1,n);
  for(int op,u,v,w,i=1;i<=q;++i){
    cin>>op>>u;
    if(op!=4) cin>>v;
    if(op==1) cin>>w;
    if(op==1) update_chain(u,v,w);
    else if(op==2) cout<<query_chain(u,v)<<'\n';
    else if(op==3) update_subtree(u,v);
    else cout<<query_subtree(u)<<'\n';
  }
}