RE+WA+MLE
我是看第一篇题解打的，思路一样，码风不同
调了一下午了呜呜呜

#include<bits/stdc++.h>

using namespace std;

typedef int ll;
const int N=3e5+50;
ll n,m,r,mod;

struct edge{
	ll to,next;
}e[N];
ll head[N],cnt;
void add_edge(int u,int v){
	++cnt;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}

ll w[N],wt[N];
ll son[N],id[N],fa[N],dep[N],siz[N],top[N],res;

ll ans[N<<2],lazy_add[N<<2];

ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}
void push_up(ll p){
	ans[p]=ans[ls(p)]+ans[rs(p)]%mod;
}

void build(ll p,ll l,ll r){
	if(l==r){ans[p]=wt[l];ans[p]=ans[p]>mod?ans[p]%mod:ans[p];return;}
	ll mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}

void change(ll p,ll l,ll r,ll add){
	lazy_add[p]=lazy_add[p]+add;
	ans[p]=(ans[p]+(r-l+1)*add)%mod;
}

void push_down(ll p,ll l,ll r){
	ll mid=(l+r)>>1;
	change(ls(p),l,mid,lazy_add[p]);
	change(rs(p),mid+1,r,lazy_add[p]);
	lazy_add[p]=0;
}

void update(ll nx,ll ny,ll l,ll r,ll p,ll k){
	if(nx<=l&&r<=ny){
		ans[p]+=(r-l+1)*k;
		lazy_add[p]+=k;
		return;
	}
	push_down(p,l,r);
	ll mid=(l+r)>>1;
	if(nx<=mid) update(nx,ny,l,mid,ls(p),k);
	if(ny>mid) update(nx,ny,mid+1,r,rs(p),k);
	push_up(p);
}

ll query(ll nx,ll ny,ll l,ll r,ll p){
	ll res=0;
	if(nx<=l&&r<=ny){return ans[p];}
	push_down(p,l,r);
	ll mid=(l+r)>>1;
	if(nx<=mid) res=res+query(nx,ny,l,mid,ls(p))%mod;
	if(ny>mid) res=res+query(nx,ny,mid+1,r,rs(p))%mod;
	return res;
}

void update_range(ll x,ll y,ll k){
	k%=mod;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		update(id[top[x]],id[x],1,n,1,k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	update(id[x],id[y],1,n,1,k);
}

ll query_range(ll x,ll y){
	ll res=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		res=res+query(id[top[x]],id[x],1,n,1)%mod;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	res=res+query(id[x],id[y],1,n,1)%mod;
	return res;
}

void update_tree(ll x,ll z){
	update(id[x],id[x]+siz[x]-1,1,n,1,z);
}

ll query_tree(ll x){
	return query(id[x],id[x]+siz[x]-1,1,n,1);
}

void dfs1(ll u,ll p){
	dep[u]=dep[p]+1;
	fa[u]=p;
	siz[u]=1;
	ll maxn=-1;
	for(int i=head[u];i;i=e[i].next){
		ll v=e[i].to;
		if(v==p) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>maxn) son[u]=v,maxn=siz[v];
	}
}

void dfs2(ll u,ll topf){
	++res;
	id[u]=res;
	wt[res]=w[u];
	top[u]=topf;
	if(!son[u]) return;
	dfs2(son[u],topf);
	for(int i=head[u];i;i=e[i].next){
		ll v=e[i].to;
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&r,&mod);
	for(int i=1;i<=m;++i) scanf("%d",&w[i]);
	for(int i=1;i<n;++i){
		ll u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v);
		add_edge(v,u);
	}
	dfs1(r,0);
	dfs2(r,r);
	build(1,1,n);
	for(int i=1;i<=m;++i){
		ll opt;
		scanf("%d",&opt);
		if(opt==1){
			ll x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			update_range(x,y,z);
		}else
		if(opt==2){
			ll x,y;
			scanf("%d%d",&x,&y);
			printf("%d\n",query_range(x,y));
		}else
		if(opt==3){
			ll x,z;
			scanf("%d%d",&x,&z);
			update_tree(x,z);
		}else{
			ll x;
			scanf("%d",&x);
			printf("%d\n",query_tree(x));
		}
	}
	return 0;
}