题目link

#include<cstdio>
#include<string>
#include<cstring> 
#include<iostream>
#include<algorithm>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int MAXN = 1e7 + 10;
int cnt=0,n,m,r,p;
int a[MAXN],dep[MAXN],f[MAXN],size[MAXN],son[MAXN],head[MAXN],id[MAXN],top[MAXN],w[MAXN];
struct edge{
	int nxt,v;
}e[MAXN<<1];
struct TREE{
	int lazy,len,sum;
}t[MAXN<<2];
void add_edge(int u,int v){
	e[++cnt].v=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void dfs1(int u,int fa){
	size[u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v!=fa){
			dep[v]=dep[u]+1;
			f[v]=u;
			dfs1(v,u);
			size[u]+=size[v];
			if(size[v]>=size[son[u]]) son[u]=v;
		}
	}
} 
void dfs2(int u,int t){
	id[u]=++cnt;
	a[cnt]=w[u];
	if(son[u]) dfs2(son[u],t);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v!=f[u]&&v!=son[u]) dfs2(v,v); 
	}
}
void build(int l,int r,int rt){
	t[rt].len=r-l+1;
	if(l==r){
		t[rt].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,lson);
	build(mid+1,r,rson);
}
void pushdown(int rt){
	if(t[rt].lazy){
		t[lson].lazy+=t[rt].lazy,t[lson].lazy%=p;
        t[rson].lazy+=t[rt].lazy,t[rson].lazy%=p;
        t[lson].sum+=t[rt].lazy*t[lson].len,t[lson].sum%=p;
        t[rson].sum+=t[rt].lazy*t[rson].len,t[rson].sum%=p;
        t[rt].lazy=0;
	}
}
void pushup(int rt){
	t[rt].sum=t[lson].sum+t[rson].sum;
}
void update(int L,int R,int c,int l,int r,int rt){
	if(L<=l&&r<=R){
		t[rt].sum+=(t[rt].len*c)%p;
		t[rt].lazy+=c;
		return ;
	}
	pushdown(rt);
	int mid=(l+r)>>1;
	if(L<=mid) update(L,R,c,l,mid,lson);
	if(r>mid) update(L,R,c,mid+1,r,rson);
	pushup(rt);
}
void update_chain(int x,int y,int z){
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(dep[fx]<dep[fy]){
			swap(x,y);
			swap(fx,fy);
		}
		update(id[fx],id[x],z,1,cnt,1);
		x=f[fx],fx=top[x];
	}
	if(id[x]>id[y]){
		swap(x,y);
	}
	update(id[x],id[y],z,1,cnt,1);
}
int query(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R) return t[rt].sum;
    pushdown(rt);
    int m=(l+r)>>1, ans=0;
    if(L<=m) ans+=query(L,R,l,m,lson)%p;
    if(R>m) ans+=query(L,R,m+1,r,rson)%p;
    return ans%p;
}
int query_chain(int x,int y){
	int ans=0,fx=top[x],fy=top[y];
	while(fx!=fy){
        if(dep[fx]<dep[fy]){
        	swap(x,y);
			swap(fx,fy);
		}
        ans+=query(id[fx],id[x],1,cnt,1);
        x=f[fx],fx=top[x];
    }
    if(id[x]>id[y]) swap(x,y);
    ans+=query(id[x],id[y],1,cnt,1);
    return ans%p;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&r,&p);
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]); 
	}
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v);
		add_edge(v,u);
	}
	f[r]=1;
	dep[r]=0;
	dfs1(r,0);
	dfs2(r,r);
	build(1,n,1);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		int lx,ly,lz;
		if(x==1){
			scanf("%d%d%d",&lx,&ly,&lz);
			update_chain(lx,ly,lz);
		}
		else if(x==2){
			scanf("%d%d",&lx,&ly);
			printf("%d\n",query_chain(lx,ly));
		}
		else if(x==3){
			scanf("%d%d",&lx,&ly);
			update(id[lx],id[lx]+size[x]-1,lz,1,n,1);
		}
		else if(x==4){
			scanf("%d",&lx); 
			printf("%d\n",query(id[lx],id[x]+size[x]-1,1,n,1));
		}
	}
	return 0;
}