树剖板子求调

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#define pii pair<int,int>
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int N=1e5+10;
long long mod,a[N],t[N*4],tag[N*4];
int siz[N],son[N],fa[N],id[N],top[N],dep[N],num;
int n,m,root;
int head[N*2],cnt;
struct Node{
	int to,next;
}edge[N*2];

void ini()
{
	for(int i=1;i<N*2;++i){head[i]=-1;edge[i].next=-1;}
}

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

void dfs1(int u,int from)
{
	siz[u]=1;fa[u]=from;dep[u]=dep[from]+1;
	for(int i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v!=from)
		{
			dfs1(v,u);
			siz[u]+=siz[v];
			if(!son[u] || siz[son[u]]<siz[v])son[u]=v;
		}
	}
}

void dfs2(int u,int topx)
{
	id[u]=++num;
	top[u]=topx;
	if(!son[u])return;
	dfs2(son[u],topx);
	for(int i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v!=fa[u] && v!=son[u])dfs2(v,v);
	}
}

void update(int k){t[k]=t[ls]+t[rs];}

void push_down(int k,int l,int r)
{
	if(!tag[k])return;
	int mid=(l+r)>>1;
	tag[ls]+=tag[k];t[ls]+=(mid-l+1)*tag[k];
	tag[rs]+=tag[k];t[rs]+=(r-mid)*tag[k];
	tag[k]=0;
	return;
}

void build(int k,int l,int r)
{
	if(l==r)
	{
		t[k]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);build(rs,mid+1,r);
	update(k);
	return;
}

void Add(int k,int l,int r,int L,int R,long long s)
{
	if(l>=L && r<=R)
	{
		tag[k]+=s;
		t[k]+=(r-l+1)*s;
		return;
	}
	int mid=(l+r)>>1;
	if(R<=mid)Add(ls,l,mid,L,R,s);
	else if(L>mid)Add(rs,mid+1,r,L,R,s);
	else {Add(ls,l,mid,L,R,s);Add(rs,mid+1,r,L,R,s);}
	update(k);
}

long long query(int k,int l,int r,int L,int R)
{
	push_down(k,l,r);
	if(l>=L && r<=R)return t[k];
	int mid=(l+r)>>1;
	if(R<=mid)return query(ls,l,mid,L,R);
	else if(L>mid)return query(rs,mid+1,r,L,R);
	else return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);
}

int main()
{ini();
	cin>>n>>m>>root>>mod;
	for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
	for(int i=1,u,v;i<n;++i)
	{
		scanf("%d%d",&u,&v);
		add_edge(u,v);add_edge(v,u);
	}
	dfs1(root,0);
	dfs2(root,root);
	build(1,1,n);
	for(int i=1,opt;i<=m;++i)
	{
		scanf("%d",&opt);
		if(opt==1)
		{
			int x,y;long long z;
			scanf("%d%d%lld",&x,&y,&z);
			while(top[x]!=top[y])
			{
				if(dep[top[x]]<dep[top[y]])swap(x,y);
				Add(1,1,n,id[top[x]],id[x],z);
				x=fa[top[x]];
			}
			if(dep[x]<dep[y])swap(x,y);
			Add(1,1,n,id[y],id[x],z);
			
		}
		else if(opt==2)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			long long ans=0;
			while(top[x]!=top[y])
			{
				if(dep[top[x]]<dep[top[y]])swap(x,y);
				ans=(ans+query(1,1,n,id[top[x]],id[x]))%mod;
				x=fa[top[x]];
			}
			if(dep[x]<dep[y])swap(x,y);
			ans=(ans+query(1,1,n,id[y],id[x]))%mod;
			printf("%lld\n",ans%mod);
		}
		else if(opt==3)
		{
			int x;long long z;
			scanf("%d%lld",&x,&z);
			Add(1,1,n,id[x],id[x]+siz[x]-1,z);
		}
		else
		{
			int x;
			scanf("%d",&x);
			printf("%lld\n",query(1,1,n,id[x],id[x]+siz[x]-1)%mod);
		}
	}
	return 0;
}