麻了

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
const int M=1e5+7;
int n,m,r,p;int ___;
int a[N],_a[N];
int son[N],fa[N],dep[N],size[N];
int top[N],dfn[N],rnk[N],bottom[N],tot;
struct zwk{
	int R,L,_add;
	struct node{
		int left_son,right_son,sum,lazy;
	}t[N<<4];
	inline void build_tree(int u,int l,int r){
		if(l==r){
			t[u].sum=_a[l];
			t[u].lazy=0;
			return;
		}
		t[u].left_son=u<<1;
		t[u].right_son=u<<1|1;
		int m=l+r>>1;
		build_tree(t[u].left_son,l,m);
		build_tree(t[u].right_son,m+1,r);
		t[u].sum=t[t[u].left_son].sum+t[t[u].right_son].sum,t[u].sum%=p;
	}
	inline void update(int u,int l,int r){
		//if(l==1&&r==5) printf("Here\n");
		if(L<=l&&r<=R){
			//if(l<=2&&2<=r) printf("update::%d %d %d\n",u,l,r); 
			//if(l<=2&&2<=r) printf("try::%d %d %d %d\n",___,l,r,_add);
			t[u].sum+=_add*(r-l+1)%p,t[u].sum%=p;
			t[u].lazy+=_add,t[u].lazy%=p;
			return;
		}
		int m=l+r>>1;
		if(t[u].lazy&&l!=r){
			//printf("down_update %d %d\n",l,r);
			//if(l<=2&&2<=r) printf("try::%d %d %d %d\n",___,l,r,_add);
			t[t[u].left_son].sum+=_add*(m-l+1)%p,t[t[u].left_son].sum%=p;
			t[t[u].right_son].sum+=_add*(r-m)%p,t[t[u].right_son].sum%=p;
			t[t[u].left_son].lazy+=_add,t[t[u].left_son].lazy%=p;
			t[t[u].right_son].lazy+=_add,t[t[u].right_son].lazy%=p;
			t[u].lazy=0;
		}
		if(L<=m) update(t[u].left_son,l,m);
		if(m<R) update(t[u].right_son,m+1,r);
		t[u].sum=t[t[u].left_son].sum+t[t[u].right_son].sum,t[u].sum%=p;
		/* 
		int lll[10]={0,1,1,4,1,3,4,5,1,2};
		int rrr[10]={0,5,3,5,2,3,4,5,1,2};
		for(int i=1;i<=9;i++)
			printf("UP::%d %d %d TRY::%d %d %d %d %d\n",u,l,r,i,lll[i],rrr[i],t[i].sum,t[i].lazy);
		*/ 
	}
	inline int query(int u,int l,int r){
		//if(l==r&&l==2) printf("try::%d\n",t[u].sum);
		if(L<=l&&r<=R)
			return t[u].sum;
		int m=l+r>>1;
		if(t[u].lazy&&l!=r){
			t[t[u].left_son].sum+=_add*(m-l+1)%p,t[t[u].left_son].sum%=p;
			t[t[u].right_son].sum+=_add*(r-m)%p,t[t[u].right_son].sum%=p;
			t[t[u].left_son].lazy+=_add,t[t[u].left_son].lazy%=p;
			t[t[u].right_son].lazy+=_add,t[t[u].right_son].lazy%=p;
			t[u].lazy=0;
		}
		int sum=0;
		if(L<=m) sum+=query(t[u].left_son,l,m);
		if(m<R) sum+=query(t[u].right_son,m+1,r);
		sum%=p;
		return sum;
	}
}tree;
struct edge{
	int nxt,v;
}e[M<<1];
int h[N],cnt;
inline void add_edge(int u,int v){
	e[++cnt].nxt=h[u],e[cnt].v=v;
	h[u]=cnt;
}
inline void dfs1(int u,int lst){
	size[u]=1;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==lst) continue;
		dep[v]=dep[u]+1;
		fa[v]=u;
		dfs1(v,u);
		if(size[v]>size[son[u]]||!son[u])
			son[u]=v;
		size[u]+=size[v];
	}
}
inline void dfs2(int u,int _top){
	//printf("%d %d\n",u,_top);
	top[u]=_top;
	dfn[u]=++tot;
	rnk[dfn[u]]=u;
	_a[dfn[u]]=a[u];
	bottom[u]=dfn[u];
	if(son[u]) dfs2(son[u],_top);
	bottom[u]=max(bottom[u],bottom[son[u]]);
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
		bottom[u]=max(bottom[u],bottom[v]);
	}
}
inline void _update(int x,int y,int z){
	while(top[x]!=top[y]){
		if(dep[x]<dep[y])
			swap(x,y);
		tree.L=dfn[top[x]],tree.R=dfn[x],tree._add=z;
		tree.update(1,1,n);
		x=fa[top[x]];
	}
	if(dfn[x]>dfn[y])
		swap(x,y);
	tree.L=dfn[x],tree.R=dfn[y],tree._add=z;
	tree.update(1,1,n);
}
inline void _query(int x,int y){
	int sum=0;
	while(top[x]!=top[y]){
		if(dep[x]<dep[y])
			swap(x,y);
		tree.L=dfn[top[x]],tree.R=dfn[x];
		sum+=tree.query(1,1,n),sum%=p;
		x=fa[top[x]];
	}
	if(dfn[x]>dfn[y])
		swap(x,y);
	tree.L=dfn[x],tree.R=dfn[y];
	sum+=tree.query(1,1,n),sum%=p;
	printf("%d\n",sum);
}
int main(){
	scanf("%d%d%d%d",&n,&m,&r,&p);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v),add_edge(v,u);
	}
	dfs1(r,0);
	dfs2(r,r);
	tree.build_tree(1,1,n);
	for(int i=1;i<=n;i++) printf("%d ",dfn[i]);printf("\n");
	//for(int i=1;i<=n;i++) printf("%d ",son[i]);printf("\n");
	//for(int i=1;i<=n;i++) printf("%d ",bottom[i]);printf("\n");
	while(m--){___++;
		int opt;
		scanf("%d",&opt);
		if(opt==1){
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			_update(x,y,z);
		}
		if(opt==2){
			int x,y;
			scanf("%d%d",&x,&y);
			_query(x,y);
			//_query(1,1);
			//_query(3,3);
		}
		if(opt==3){
			int x,z;
			scanf("%d%d",&x,&z);
			//printf("3::%d %d\n",dfn[x],bottom[x]);
			tree.L=dfn[x],tree.R=bottom[x],tree._add=z;
			tree.update(1,1,n);
		}
		if(opt==4){
			int x;
			scanf("%d",&x);
			//printf("%d %d\n",dfn[x],bottom[x]);
			tree.L=dfn[x],tree.R=bottom[x];
			//tree.L=1,tree.R=5;
			printf("%d\n",tree.query(1,1,n));
		}
		//if(opt==3) printf("A:"),_query(1,1);
		/* 
		int lll[10]={0,1,1,4,1,3,4,5,1,2};
		int rrr[10]={0,5,3,5,2,3,4,5,1,2};
		for(int i=1;i<=9;i++)
			printf("TRY::%d %d %d %d %d\n",i,lll[i],rrr[i],tree.t[i].sum,tree.t[i].lazy);
		*/
	}
	return 0;
}
/*
5 2 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
1 5 1 3
2 1 3
*/
/*
5 5 2 24
7 3 7 8 0 
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3
*/
/*
5 2 1 10000
0 0 0 0 0
1 2
2 3
1 4
4 5
1 3 5 1
4 1 
*/