玩原神玩多了 树剖求调

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n,m,r,p,X,Y,op,z;
const ll MAX = 3e5+10;
ll w[MAX],f[MAX],son[MAX],id[MAX],top[MAX],dep[MAX],size[MAX];
ll c1[MAX],c2[MAX];
vector <ll> edge[MAX];
namespace graph{
	void add(ll from,ll to){
		edge[from].emplace_back(to);
		edge[to].emplace_back(from);
	}
}
namespace bit{
	ll lowb1t(ll x){return x&-x;}
	void add1(ll x,ll k){
		for(int i=x;i<=n;i+=lowb1t(i)){
			c1[i]+=x;
			c2[i]+=k*x;
		}
	}
	void add(ll l,ll r,ll v){
		add1(l,v);
		add1(r+1,-v);
	}
	ll query1(ll x){
		ll res=0;
		for(int i=x;i;i-=lowb1t(i)){
			res+=c1[i]*(x+1ll);
			res-=c2[i];
		}
		return res;
	}
	ll query(ll l,ll r){return query1(r)-query1(l-1);}
}
ll cnt;
namespace dfs{
	void dfs1(ll now,ll fa){
		f[now]=fa;
		size[now]=1;
		dep[now]=dep[fa]+1;
		ll maxson=-1;
		for(auto &&e : edge[now]){
			if(e==fa) continue;
			dfs1(e,now);
			size[now]+=size[e];
			if(size[e]>maxson){
				maxson=size[e];
				son[now]=e;
			}
		}
	}
	void dfs2(ll now,ll tp){
		top[now]=tp;
		id[now]=++cnt;
		if(w[now]!=0) bit::add(id[now],id[now],w[now]);
		if(!son[now]) return ;
		dfs2(son[now],tp);
		for(auto &&e:edge[now]){
			if(e==son[now] or e==f[now]) continue;
			dfs2(e,e);
		}
	}
}
namespace oper{
	ll querypath(ll u,ll v){
		ll res=0;
	//	k%=p;
		while(top[v]!=top[u]){
			if(dep[top[u]]<dep[top[v]]) swap(u,v);
			res=(res+bit::query(id[top[u]],id[u]))%p;
			u=f[top[u]];
		}
		if(dep[u]>dep[v]) swap(u,v);
		res=(res+bit::query(id[u],id[v]))%p;
		return res%p;
	}
	void addpath(ll u,ll v,ll k){
	//	ll res=0;
			k%=p;
		while(top[v]!=top[u]){
			if(dep[top[u]]<dep[top[v]]) swap(u,v);
			bit::add(id[top[u]],id[u],k);
			u=f[top[u]];
		}
		if(dep[u]>dep[v]) swap(u,v);
		bit::add(id[u],id[v],k);
	}
	void addson(ll u,ll k){
		k%=p;
		bit::add(id[u],id[u]+size[u]-1,k);
	}
	 ll queryson(ll u){
		 return bit::query(id[u],id[u]+size[u]-1)%p;
	 }
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>r>>p;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<n;i++){
		cin>>X>>Y;
		graph::add(X,Y);
	}
	dfs::dfs1(r,0);
	dfs::dfs2(r,r);
	while(m--){
		cin>>op>>X;
		if(op==1){
			cin>>Y>>z;
			oper::addpath(X,Y,z);
		} else if(op==2){
			cin>>Y;
			cout<<oper::querypath(X,Y)<<'\n';
		} else if(op==3){
			cin>>Y;
			oper::addson(X,Y);
		} else{
			cout<<oper::queryson(X)<<'\n';
		}
	}
	return 0;
}