37ptsWA求条

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll MOD;
ll n,m,r,a[N],b[N];
vector<ll> e[N];
struct segtree{
	ll tr[4*N],l[4*N],r[4*N],laz[4*N];
	void init(ll u,ll L,ll R){
		l[u]=L,r[u]=R,laz[u]=0;
		if(L==R){
			tr[u]=a[L];
			tr[u]%=MOD;
			return ;
		}
		ll mid=(L+R)/2;
		init(u*2,L,mid),init(u*2+1,mid+1,R);
		tr[u]=tr[u*2]+tr[u*2+1];
		tr[u]%=MOD;
	}
	void build(){init(1,1,n);}
	void lazdown(ll u){
		if(l[u]==r[u]||!laz[u])return ;
		tr[u*2]+=laz[u]*(r[u*2]-l[u*2]+1),tr[u*2]%=MOD;
		tr[u*2+1]+=laz[u]*(r[u*2+1]-l[u*2+1]+1),tr[u*2+1]%=MOD;
		laz[u*2]+=laz[u],laz[u*2]%=MOD;
		laz[u*2+1]+=laz[u],laz[u*2+1]%=MOD;
		laz[u]=0; 
	}
	void A(ll u,ll L,ll R,ll val){
		lazdown(u);
		if(l[u]>=L&&r[u]<=R){
			tr[u]+=val*(r[u]-l[u]+1),tr[u]%=MOD;
			laz[u]+=val,laz[u]%=MOD;
			return ;
		}
		if(l[u]>R||r[u]<L)return ;
		A(u*2,L,R,val),A(u*2+1,L,R,val);
        tr[u]=tr[u*2]+tr[u*2+1],tr[u]%=MOD;
	}
	void add(ll L,ll R,ll val){A(1,L,R,val);}
	ll Q(ll u,ll L,ll R){
		lazdown(u);
		if(l[u]>=L&&r[u]<=R)return tr[u];
		if(l[u]>R||r[u]<L)return 0;
		return (Q(u*2,L,R)+Q(u*2+1,L,R))%MOD;
	}
	ll query(ll L,ll R){return Q(1,L,R);}
}tr;
ll fa[N],dep[N],siz[N],son[N],id[N],top[N];
void dfs1(ll u,ll f,ll deep){
	fa[u]=f,dep[u]=deep,siz[u]=1;
	for(auto i:e[u]){
		if(i==f)continue;
		dfs1(i,u,deep+1);
		siz[u]+=siz[i];
		if(siz[son[u]]<siz[i])son[u]=i;
	}
}
ll cnt=0;
void dfs2(ll u,ll topf){
	cnt++;
	top[u]=topf,id[u]=cnt;
	a[cnt]=b[u];
	if(son[u])dfs2(son[u],topf);
	for(auto i:e[u])if(i!=fa[u]&&i!=son[u])dfs2(i,i);
}
void add(ll x,ll y,ll val){
	while(top[x]!=top[y]){
		if(dep[x]<dep[y])x^=y,y^=x,x^=y;
		tr.add(id[top[x]],id[x],val);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])x^=y,y^=x,x^=y;
	tr.add(id[y],id[x],val);
}
ll query(ll x,ll y){
	ll ans=0;
	while(top[x]!=top[y]){
		if(dep[x]<dep[y])x^=y,y^=x,x^=y;
		ans+=tr.query(id[top[x]],id[x]),ans%=MOD;
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])x^=y,y^=x,x^=y;
	ans+=tr.query(id[y],id[x]),ans%=MOD;
	return ans;
}
int main(){
    std::ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>r>>MOD;
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n-1;i++){
		ll u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(r,r,0);
	dfs2(r,r);
	tr.build();
	for(int i=1;i<=m;i++){
		ll c,x,y,z;
		cin>>c;
		if(c==1){
			cin>>x>>y>>z;
			add(x,y,z);
		}
		if(c==2){
			cin>>x>>y;
			cout<<query(x,y)<<"\n";
		}
		if(c==3){
			cin>>x>>z;
			tr.add(id[x],id[x]+siz[x]-1,z);
		}
		if(c==4){
			cin>>x;
			cout<<tr.query(id[x],id[x]+siz[x]-1)<<"\n";
		}
	}
	return 0;
}