#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<iomanip> #include<algorithm> #include<ctime> #include<queue> #define rg register #define lst long long #define N 100050 #define ls (now<<1) #define rs (now<<1|1) using namespace std; int n,m,root,p,cnt,ss,ans; struct EDGE{ int to,nxt; }edge[N<<1]; struct TREE{ int l,r,siz,sum,lazy; }ljl[N<<2]; int first[N],v[N]; int fa[N],deep[N],son[N],size[N],top[N],num[N],vv[N]; inline int read() { rg int s=0,m=1;rg char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')m=-1,ch=getchar(); while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar(); return s*m; } inline void add(rg int p,rg int q){edge[++cnt]=(EDGE){q,first[p]};first[p]=cnt;} void init()//输入点权和加边 { n=read(),m=read(),root=read(),p=read(); for(rg int i=1;i<=n;++i)v[i]=read(),size[i]=1; for(rg int i=1;i<n;++i) { rg int p=read(),q=read(); add(p,q),add(q,p); } } //______________________________________________输入，加边 void dfs_1(rg int now,rg int dep,rg int fm)//Dfs预处理 父亲节点 深度 子树大小 { rg int kk=0;//辅助找重儿子 fa[now]=fm,deep[now]=dep;//父亲，深度 for(rg int i=first[now];i;i=edge[i].nxt)//枚举儿子节点(边) { rg int qw=edge[i].to;//儿子 if(qw==fm)continue; dfs_1(qw,dep+1,now);//继续去找 size[now]+=size[qw];//处理子树大小 if(size[qw]>kk)kk=size[qw],son[now]=qw;//找重儿子 } } void dfs_2(rg int now,rg int up)//找新的dfs序vv 处理now在dfs序中的位置num 所在重链的顶端 { num[now]=++ss,top[now]=up,vv[ss]=v[now];//如上 if(son[now])dfs_2(son[now],top[now]);//先递归找重儿子 for(rg int i=first[now];i;i=edge[i].nxt)//再找其他儿子(边) { rg int qw=edge[i].to; if(qw!=fa[now]&&qw!=son[now])//如上 dfs_2(qw,qw); } } //__________________________________________________________dfs预处理 inline void Pushup(rg int now)//处理一下和 { ljl[now].sum=(ljl[ls].sum+ljl[rs].sum+p)%p; } inline void Pushdown(rg int now)//lazy标记下放 { if(ljl[now].lazy) { ljl[ls].sum+=ljl[ls].siz*ljl[now].lazy;ljl[ls].sum%=p; ljl[rs].sum+=ljl[rs].siz*ljl[now].lazy;ljl[rs].sum%=p; ljl[ls].lazy+=ljl[now].lazy;ljl[ls].lazy%=p; ljl[rs].lazy+=ljl[now].lazy;ljl[rs].lazy%=p; ljl[now].lazy=0; } } void build(rg int now,rg int ll,rg int rr)//建线段树 { ljl[now]=(TREE){ll,rr,rr-ll+1}; if(ll==rr){ljl[now].sum=vv[ll];return;} rg int mid=(ll+rr)>>1; build(ls,ll,mid),build(rs,mid+1,rr); Pushup(now); } void update(rg int now,rg int ll,rg int rr ,rg int xx)//区间ll到rr上加一个xx { if(ljl[now].l>=ll&&ljl[now].r<=rr) { ljl[now].sum+=ljl[now].siz*xx; ljl[now].lazy+=xx;return; } Pushdown(now); rg int mid=(ljl[now].l+ljl[now].r)/2; if(rr<=mid)update(ls,ll,rr,xx); if(ll>mid)update(rs,ll,rr,xx); if(ll<=mid&&rr>mid) update(ls,ll,mid,xx),update(rs,mid+1,rr,xx); Pushup(now); } int Query(rg int now,rg int ll,rg int rr)//求ll到rr区间的和 { rg int s=0; if(ljl[now].l>=ll&&ljl[now].r<=rr)return ljl[now].sum; Pushdown(now); rg int mid=(ljl[now].l+ljl[now].r)>>1; if(rr<=mid)s+=Query(ls,ll,rr); if(ll>mid) s+=Query(rs,ll,rr); if(ll<=mid&&rr>mid) s+=Query(ls,ll,mid)+Query(rs,mid+1,rr); Pushup(now),s%=p; return s; } //__________________________________________________________线段树 inline void tree_work(rg int x,rg int y,rg int z,rg int op) { if(num[x]>num[y])swap(x,y); if(!op)update(1,num[x],num[y],z); else ans+=Query(1,num[x],num[y]);ans%=p; } inline void tree_Work(rg int x,rg int y,rg int z,rg int op) { while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]])swap(x,y); tree_work(top[x],x,z,op); x=fa[top[x]]; } tree_work(x,y,z,op); } inline void ANS() { for(rg int i=1;i<=m;++i) { rg int type=read();ans=0; if(type==1){rg int x=read(),y=read(),z=read(); tree_Work(x,y,z,0);} if(type==2){rg int x=read(),y=read(); tree_Work(x,y,0,1);} if(type==3){rg int x=read(),z=read(); update(1,num[x],num[x]+size[x]-1,z);} if(type==4){rg int x=read(); ans=Query(1,num[x],num[x]+size[x]-1);} if(type==2||type==4)printf("%d ",ans); } } int main() { init(); dfs_1(root,0,0); dfs_2(root,root); build(1,1,ss); ANS(); return 0; }