树剖模板 28pts 求条，only AC #2#3#11

#include<bits/stdc++.h>
using namespace std;

#define int long long
int n,q,root,mod,opt,x,y,z,a[100005],val[100005];
vector<int> e[100005];
int dep[100005],siz[100005],hvy[100005],fa[100005];
int top[100005],id[100005],cnt;
int t[400005],b[400005];

void build(int l,int r,int p){
	if(l==r){
		t[p]=val[l]%mod;
		return;
	}
	int mid=l+r>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
	t[p]=(t[p<<1]+t[p<<1|1])%mod;
	return;
}

void pushdown(int l,int r,int p){
	if(!b[p]) return;
	int mid=l+r>>1;
	t[p<<1]=(t[p<<1]+(mid-l+1)*b[p]%mod)%mod;
	t[p<<1|1]=(t[p<<1|1]+(r-mid)*b[p]%mod)%mod;
	b[p<<1]=(b[p<<1]+b[p])%mod;
	b[p<<1|1]=(b[p<<1|1]+b[p])%mod;
	b[p]=0;
	return;
}

void add(int l,int r,int p,int x,int y,int z){
	if(x<=l&&r<=y){
		t[p]=(t[p]+z*(r-l+1)%mod)%mod;
		b[p]=(b[p]+z)%mod;
		return;
	}
	pushdown(l,r,p);
	int mid=l+r>>1;
	if(x<=mid) add(l,mid,p<<1,x,y,z);
	if(y>mid) add(mid+1,r,p<<1|1,x,y,z);
	t[p]=(t[p<<1]+t[p<<1|1])%mod;
	return;
}

int query(int l,int r,int p,int x,int y){
	if(x<=l&&r<=y) return t[p];
	pushdown(l,r,p);
	int mid=l+r>>1,res=0;
	if(x<=mid) res=(res+query(l,mid,p<<1,x,y))%mod;
	if(y>mid) res=(res+query(mid+1,r,p<<1|1,x,y))%mod;
	return res;
}

void addPath(int x,int y,int z){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		add(1,n,1,id[top[x]],x,z);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])
		swap(x,y);
	add(1,n,1,id[y],id[x],z);
	return;
}

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

void dfs1(int u,int f){
	fa[u]=f;dep[u]=dep[f]+1;int mx=0;
	for(auto v:e[u]){
		if(v==f) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[hvy[u]]) hvy[u]=v;
	}
	++siz[u];return;
}

void dfs2(int u,int head){
	top[u]=head;id[u]=++cnt;val[cnt]=a[u];
	if(!hvy[u]) return;
	dfs2(hvy[u],head);
	for(auto v:e[u]){
		if(v==hvy[u]||v==fa[u]) continue;
		dfs2(v,v);
	}
	return;
}

signed main(){
	cin>>n>>q>>root>>mod;
	for(int i=1;i<=n;i++)	
		cin>>a[i];
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(root,0);
	dfs2(root,root);
	build(1,n,1);
	while(q--){
		cin>>opt;
		if(opt==1){
			cin>>x>>y>>z;
			addPath(x,y,z);
		}else if(opt==2){
			cin>>x>>y;
			cout<<queryPath(x,y)%mod<<endl;
		}else if(opt==3){
			cin>>x>>y;
			add(1,n,1,id[x],id[x]+siz[x]-1,y);
		}else{
			cin>>x;
			cout<<(query(1,n,1,id[x],id[x]+siz[x]-1)+mod)%mod<<endl;
		}
	}
	return 0;
}