```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define REP(i,s,e) for(int i=s;i>=e;i--)
#define LL long long
#define U unsigned
const int N=1e5+10;
int n,m,root;LL mod,a[N];
int head[N],f[N][30],d[N],id[N],rk[N],sz[N],son[N],t[N],gsz,now;
struct node{int to,nxt;}g[N<<1];
void add(int u,int v){g[++gsz]={v,head[u]},head[u]=gsz;}
void dfs1(int x,int fa,int dep){
f[x][0]=fa,d[x]=dep,sz[x]=1;
rep(i,1,20)f[x][i]=f[f[x][i-1]][i-1];
for(int i=head[x];i!=-1;i=g[i].nxt){
if(g[i].to!=fa){
dfs1(g[i].to,x,dep+1);
sz[x]+=sz[g[i].to];
if(sz[g[i].to]>sz[son[x]])son[x]=g[i].to;
}
}
}
void dfs2(int x,int fa,int top){
id[x]=++now,rk[now]=x,t[x]=top;
if(son[x]){
dfs2(son[x],x,top);
for(int i=head[x];i!=-1;i=g[i].nxt)if(g[i].to!=fa&&g[i].to!=son[x])dfs2(g[i].to,x,g[i].to);
}
}
int lca(int u,int v){
if(d[u]>d[v])swap(u,v);
REP(i,20,0)if(d[v]-(1<<i)>=d[u])v=f[v][i];
if(u==v)return u;
REP(i,20,0)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
return f[u][0];
}
#define lson (p<<1)
#define rson (p<<1|1)
struct tree{
int l,r;
LL sum,lazy;
void add(LL k){sum=(sum+k*(r-l+1))%mod,lazy=(lazy+k)%mod;}
}tr[N*4];
inline tree merge(const tree &x,const tree &y){return {x.l,y.r,(x.sum+y.sum)%mod,0};}
inline void spread(const int &p){tr[lson].add(tr[p].lazy),tr[rson].add(tr[p].lazy),tr[p].lazy=0;}
void build(int p,int l,int r){
if(l==r){tr[p]={l,r,a[rk[l]],0};return;}
int mid=(l+r)>>1;
build(lson,l,mid),build(rson,mid+1,r);
tr[p]=merge(tr[lson],tr[rson]);
}
tree ask(int p,int l,int r){
spread(p);
if(l<=tr[p].l&&tr[p].r<=r)return tr[p];
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid&&r>mid)return merge(ask(lson,l,r),ask(rson,l,r));
if(l<=mid)return ask(lson,l,r);
if(r>mid) return ask(rson,l,r);
}
void change(int p,int l,int r,LL k){
spread(p);
if(l<=tr[p].l&&tr[p].r<=r){tr[p].add(k);return;}
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid)change(lson,l,r,k);
if(r>mid) change(rson,l,r,k);
tr[p]=merge(tr[lson],tr[rson]);
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d%d%d%lld",&n,&m,&root,&mod);
rep(i,1,n)scanf("%lld",a+i),a[i]%=mod;
int u,v,w,to,opt;LL k,cnt;
rep(i,1,n-1){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs1(root,0,1),dfs2(root,0,root),build(1,1,n);
while(m--){
scanf("%d",&opt);
if(opt==1){
scanf("%d%d%lld",&u,&v,&k);
k%=mod,w=lca(u,v);
while(d[u]>=d[w]){
to=t[u];if(d[w]>d[to])to=w;
change(1,id[to],id[u],k),u=f[to][0];
}
while(d[v]>=d[w]){
to=t[v];if(d[w]>d[to])to=w;
change(1,id[to],id[v],k),v=f[to][0];
}
change(1,id[w],id[w],mod-k);
}
if(opt==2){
scanf("%d%d",&u,&v);
cnt=0,w=lca(u,v);
while(d[u]>=d[w]){
to=t[u];if(d[w]>d[to])to=w;
cnt=(ask(1,id[to],id[u]).sum+cnt)%mod;
u=f[to][0];
}
while(d[v]>=d[w]){
to=t[v];if(d[w]>d[to])to=w;
cnt=(ask(1,id[to],id[v]).sum+cnt)%mod;
v=f[to][0];
}
cnt=(mod+cnt-ask(1,id[w],id[w]).sum)%mod;
printf("%lld\n",cnt);
}
if(opt==3){
scanf("%d%lld",&u,&k);k%=mod;
change(1,id[u],id[u]+sz[u]-1,k);
}
if(opt==4){
scanf("%d",&u);
printf("%lld\n",ask(1,id[u],id[u]+sz[u]-1).sum);
}
}
return 0;
}
```
这是四倍空间的代码，六倍空间就是把第43行
```
}tr[N*4]
```
改为
```
}tr[N*6]
```
by hhhwg07 @ 2022-03-23 22:00:49
<https://studyingfather.blog.luogu.org/why-cannot-you-make-a-good-title>
by rxjdasiwzl @ 2022-03-23 22:44:58
@[hhhwg07](/user/136816)
```cpp
spread(p);
if(l<=tr[p].l&&tr[p].r<=r){tr[p].add(k);return;}
```
两行交换一下，否则在叶子结点pushdown的时候会访问到不存在的节点
by devout @ 2022-03-24 19:23:47
其他函数同理
by devout @ 2022-03-24 19:24:05
已过，本贴结
by hhhwg07 @ 2022-03-25 07:57:25