```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long read(){
long long x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
void write(long long x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
const int N=1e5+10;
#define pl p<<1
#define pr p<<1|1
#define pf a[p].fa
#define pde a[p].dep
#define psi a[p].sze
#define pte a[p].ted
#define pdf a[p].dfn
#define pso a[p].son
#define pt a[p].top
#define pc a[p].ced
#define TCP_T ll
int head[2*N],nxt[2*N],ver[2*N],tot;
void add(int x,int y){
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
const TCP_T inf=1e9;
int cnt,rnk[N],n,w[N];
int m,r,P;
struct Segment_Tree{
struct Tree{
int l,r;
TCP_T tag;
TCP_T sum;
}a[N*4];
void pushup(int p){
a[p].sum=(a[pl].sum+a[pr].sum)%P;
}
void pushdown(int p){
if(a[p].tag){
a[pl].sum=(a[pl].sum+(a[pl].r-a[pl].l+1)*a[p].tag%P)%P;
a[pr].sum=(a[pr].sum+(a[pr].r-a[pr].l+1)*a[p].tag%P)%P;
a[pl].tag=(a[pl].tag+a[p].tag)%P;
a[pr].tag=(a[pr].tag+a[p].tag)%P;
a[p].tag=0;
}
}
void build(int p,int l,int r){
a[p].l=l;
a[p].r=r;
if(l==r){
a[p].sum=w[rnk[l]];
return;
}
int mid=(l+r)>>1;
build(pl,l,mid);
build(pr,mid+1,r);
pushup(p);
}
void change(int p,int l,int r,TCP_T v){
if(l<=a[p].l&&a[p].r<=r){
a[p].tag=(a[p].tag+v)%P;
a[p].sum=(a[p].sum+(a[p].r-a[p].l+1)*v%P)%P;
return;
}
pushdown(p);
int mid=(a[p].l+a[p].r)>>1;
if(l<=mid)
change(pl,l,r,v);
if(r>mid)
change(pr,l,r,v);
pushup(p);
}
TCP_T ask(int p,int l,int r){
if(l<=a[p].l&&a[p].r<=r)
return a[p].sum%P;
pushdown(p);
int mid=(a[p].l+a[p].r)>>1;
TCP_T ans=0;
if(l<=mid)
ans=(ans+ask(pl,l,r))%P;
if(r>mid)
ans=(ans+ask(pr,l,r))%P;
return ans;
}
}tree;
struct TCP{
struct Node{
int fa,dep,dfn;//self
int sze,ted;//tree
int son,top,ced;//chain
}a[N];
void dfs1(int p){
pso=-1;
psi=1;
for(int i=head[p];i;i=nxt[i]){
int y=ver[i];
if(!a[y].dep){
a[y].dep=pde+1;
a[y].fa=p;
dfs1(y);
psi+=a[y].sze;
if(pso==-1||a[y].sze>a[pso].sze)
pso=y;
}
}
}
int dfs2(int p,int q){
pt=q;
pdf=++cnt;
rnk[cnt]=pte=p;
if(pso==-1){
pc=cnt;
while(p!=q){
p=pf;
pc=cnt;
}
return pte;
}
pte=dfs2(pso,q);
for(int i=head[p];i;i=nxt[i]){
int y=ver[i];
if(y!=pso&&y!=pf)
pte=dfs2(y,y);
}
return pte;
}
void init(int root){
cnt=0;
a[root].dep=1;
dfs1(root);
dfs2(root,root);
tree.build(1,1,n);
}
void change1(int u,int v,TCP_T z){
int fu=a[u].top,fv=a[v].top;
while(fu^fv){
if(a[fu].dep>=a[fv].dep){
tree.change(1,a[fu].dfn,a[u].dfn,z);
u=a[fu].fa;
}
else{
tree.change(1,a[fv].dfn,a[v].dfn,z);
v=a[fv].fa;
}
fu=a[u].top;
fv=a[v].top;
}
tree.change(1,min(a[u].dfn,a[v].dfn),max(a[u].dfn,a[v].dfn),z);
}
void change2(int p,TCP_T z){
tree.change(1,pdf,a[pte].dfn,z);
}
TCP_T ask1(int u,int v){
TCP_T ans=0;
int fu=a[u].top,fv=a[v].top;
while(fu^fv){
if(a[fu].dep>=a[fv].dep){
ans=(ans+tree.ask(1,a[fu].dfn,a[u].dfn))%P;
u=a[fu].fa;
}
else{
ans=(ans+tree.ask(1,a[fv].dfn,a[v].dfn))%P;
v=a[fv].fa;
}
fu=a[u].top;
fv=a[v].top;
}
ans=(ans+tree.ask(1,min(a[u].dfn,a[v].dfn),max(a[u].dfn,a[v].dfn)))%P;
return ans;
}
TCP_T ask2(int p){
return tree.ask(1,pdf,a[pte].dfn)%P;
}
}tr;
int main(){
n=read();m=read();r=read();P=read();
for(int i=1;i<=n;i++)
w[i]=read()%P;
for(int i=1,a,b;i<n;i++){
a=read();b=read();
add(a,b);
add(b,a);
}
tr.init(r);
ll c,a,b;
for(int i=1,op;i<=m;i++){
op=read();a=read();
switch(op){
case 1:b=read();c=read()%P;tr.change1(a,b,c);break;
case 2:b=read();write(tr.ask1(a,b));putchar('\n');break;
case 3:b=read()%P;tr.change2(a,b);break;
case 4:write(tr.ask2(a));putchar('\n');break;
}
}
return 0;
}
```
by chenjunxiu @ 2022-01-14 11:16:55