Rt

代码：

#include<bits/stdc++.h>
#define int long long
#define mod(fst) ((fst)<p?(fst):((fst)-p))
#define mid ((l+r)>>1)
#define lson (rt)<<1,l,mid
#define rson (rt)<<1|1,mid+1,r
using namespace std;
const int N=1e6+10; 
struct node
{
  int v,next;
}e[N*2];
int n,p,dep[N],id[N],lazy[N<<2],sum[N<<2],Size[N],dat[N],tot,head[N],f[N],son[N],top[N],cnt,dati[N];
void add(int u,int v)
{
  e[++tot].v=v,e[tot].next=head[u],head[u]=tot; 
}
void dfs(int now,int fa)
{
  f[now]=fa;dep[now]=dep[fa]+1; 
  son[now]=0; Size[now]=1; 
  for(int i=head[now];i;i=e[i].next)
  {
    int v=e[i].v;
    if(v!=fa) 
    {
      dfs(v,now);
      Size[now]+=Size[v];
      if(Size[v]>Size[son[now]]) son[now]=v; 
    }
  }
}
void dfs2(int now,int topi)
{
  top[now]=topi;
  id[now]=++cnt; //dfn 序 
  dati[cnt]=dat[now]; 
  if(!son[now]) return ;
  dfs2(son[now],topi);
  for(int i=head[now];i;i=e[i].next)
  {

    int v=e[i].v;
    if(v!=f[now]&&v!=son[now])
    {
      dfs2(v,v); 
    }
  }
}
void build(int rt,int l,int r)
{
  if(l==r) 
  {
    sum[rt]=dati[l];
    return ;
  }
  build(lson);
  build(rson);
  sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 
}
void pushdown(int rt,int l,int r)
{
  lazy[rt<<1]=mod(lazy[rt<<1]+lazy[rt]);
  lazy[rt<<1|1]=mod(lazy[rt<<1|1]+lazy[rt]);
  sum[rt<<1]=mod(sum[rt<<1]+(mid-l+1)*lazy[rt]%p);
  sum[rt<<1|1]=mod(sum[rt<<1|1]+(r-mid)*lazy[rt]%p);
  lazy[rt]=0; 
}
void change(int rt,int l,int r,int L,int R,int Z)
{
  if(L<=l&&R>=r)
  {
    lazy[rt]=mod(lazy[rt]+Z);
    sum[rt]=mod(sum[rt]+(r-l+1)*Z%p); 
    return ; 
  }
  if(lazy[rt])pushdown(rt,l,r); 
  if(L<=mid) change(lson,L,R,Z);
  if(R>mid) change(rson,L,R,Z);
  sum[rt]=mod(sum[rt<<1]+sum[rt<<1|1]); 
}
int query(int rt,int l,int r,int L,int R)
{
  if(L<=l&&R>=r) return mod(sum[rt]);
  if(lazy[rt])pushdown(rt,l,r);
  int ans=0; 
  if(L<=mid) ans=mod(ans+query(lson,L,R));
  if(R>mid) ans=mod(ans+query(rson,L,R));
  return ans; 
}
void Xchange(int x,int y,int z)
{
  while(top[x]!=top[y])
  {
    if(dep[top[x]]<dep[top[y]]) swap(x,y);
    change(1,1,n,id[top[x]],id[x],z); x=f[top[x]]; 
  }
  if(dep[x]>dep[y])swap(x,y);
  change(1,1,n,id[x],id[y],z); 
}
int Xsum(int x,int y)
{
  int ans=0;
  while(top[x]!=top[y])
  {
    if(dep[top[x]]<dep[top[y]]) swap(x,y);
    ans=mod(ans+query(1,1,n,id[top[x]],id[x]));
    x=f[top[x]]; 
  }
  if(dep[x]>dep[y]) swap(x,y);
  ans=mod(ans+query(1,1,n,id[x],id[y])); 
  return ans; 
}
void Ychange(int x,int k)
{
  change(1,1,n,id[x],id[x]+Size[x]-1,k); 
}
int Ysum(int x)
{
  return query(1,1,n,id[x],id[x]+Size[x]-1); 
}
signed main()
{ //luogu nmsl!!
  int m,r; 
  scanf("%lld%lld%lld%lld",&n,&m,&r,&p);
  for(int i=1;i<=n;++i) scanf("%lld",&dat[i]);
  for(int i=1;i<n;++i)
  {
    int x,y;
    scanf("%lld%lld",&x,&y); 
    add(x,y); add(y,x); 
  }
  dfs(r,r); dfs2(r,r); 
  build(1,1,n); 
  for(int i=1;i<=m;++i)
  {
    int opt,x,y,z; scanf("%lld",&opt);
    if(opt==1)
    {
      scanf("%lld%lld%lld",&x,&y,&z);
      Xchange(x,y,z); 
    }
    else if(opt==2)
    {
      scanf("%lld%lld",&x,&y);
      printf("%lld\n",Xsum(x,y)); 
    }
    else if(opt==3)
    {
      scanf("%lld%lld",&x,&z);
      Ychange(x,z); 
    }
    else if(opt==4)
    {
      scanf("%lld",&x);
      printf("%lld\n",Ysum(x)); 
    }
    // for(int j=1;j<=n;++j) printf("%lld ",query(1,1,n,id[j],id[j])) ; 
    // puts(""); 
  }
  return 0 ; 
}