萌新刚学OI一天树剖求跳。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,p,r,X=0;
const int maxn=200005;
vector<int>G[maxn];
int size[maxn];
int top[maxn];
int son[maxn];
int New[maxn];
int Old[maxn];
int fa[maxn];
int in[maxn],out[maxn];
int depth[maxn];
int A[maxn];
struct Segment{
	long long a[maxn],w[2*maxn],lzy[2*maxn];
	void pushup(int u)
	{
		w[u]=(w[u*2]+w[u*2+1])%p;
	}
	void build(int u=1,int l=1,int r=n)
	{
		if(l==r)
		{
			w[u]=a[l]%p;
			return;
		}
		int m=(l+r)/2;
		build(u*2,l,m),build(u*2+1,m+1,r);
		pushup(u);
	}
	bool InRange(int L,int R,int l,int r)
	{
		return (l<=L)&&(R<=r);
	}
	bool OutofRange(int L,int R,int l,int r)
	{
		return (L>r)||(R<l);
	}
	void maketag(int u,int len,long long x)
	{
		lzy[u]+=x;lzy[u]%=p;
		w[u]+=len*x;w[u]%=p;
	}
	void pushdown(int u,int l,int r)
	{
		int m=(l+r)/2;
		maketag(u*2,m-l+1,lzy[u]);
		maketag(u*2+1,r-m,lzy[u]);
		lzy[u]=0;
	}
	int query(int l,int r,int u=1,int L=1,int R=n)
	{
		if(InRange(L,R,l,r)) return w[u];
		else if(!OutofRange(L,R,l,r))
		{
			int m=(L+R)/2;
			pushdown(u,L,R);
			return (query(l,r,u*2,L,m)+query(l,r,u*2+1,m+1,R))%p;
		}
		else return 0;
	}
	void update(int l,int r,long long x,int u=1,int L=1,int R=n)
	{
		if(InRange(L,R,l,r)) maketag(u,R-L+1,x);
		else if(!OutofRange(L,R,l,r))
		{
			int m=(L+R)/2;
			pushdown(u,L,R);
			update(l,r,x,u*2,L,m);
			update(l,r,x,u*2+1,m+1,R);
			pushup(u);
		}
	}
};
Segment a;
int dfs(int x,int fat)//拍成DFS序
{
	fa[x]=fat;
	in[x]=out[x]=X+1;
	New[x]=++X;Old[X]=x;a.a[X]=A[x];
	size[x]=1;
	depth[x]=depth[fat]+1;
	for(int i=0;i<(int)G[x].size();i++)
	{
		if(fat!=G[x][i]) size[x]+=dfs(G[x][i],x);
		if(x!=fat&&size[G[x][i]]>size[G[x][son[x]]]) son[x]=i;//重儿子
	}
	out[x]=in[x]+size[x]-1;
	return size[x];//子树大小
}
void Dfs(int x,int Top)//求链顶
{
	top[x]=Top;
	for(int i=0;i<(int)G[x].size();i++)
	{
		if(i==son[x]&&G[x][son[x]]!=fa[x]) Dfs(G[x][son[x]],Top);
		if(i!=son[x]&&fa[x]!=G[x][i]) Dfs(G[x][i],G[x][i]);
	}
}
signed main()
{
	int T;
	cin>>n>>T>>r>>p;
	for(int i=1;i<=n;i++) cin>>A[i];
	for(int i=1;i<n;i++)
	{
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	depth[0]=0;top[r]=r;
	dfs(r,0);
	Dfs(r,r);
	a.build();
	while(T--)
	{
		int op,x,y,z;
		cin>>op>>x;
		if(op==1)
		{
			cin>>y>>z;z%=p;
			while(top[x]!=top[y])
			{
				if(depth[top[x]]<depth[top[y]]) swap(x,y);
				a.update(New[top[x]],New[x],z),x=fa[top[x]];
			}
			if(depth[x]>depth[y]) swap(x,y);
			a.update(New[x],New[y],z);
		}
		if(op==2)
		{
			int ans=0;
			cin>>y;
			while(top[x]!=top[y])
			{
				if(depth[top[x]]<depth[top[y]]) swap(x,y);
				ans+=a.query(New[top[x]],New[x]),x=fa[top[x]],ans%=p;
			}
			if(depth[x]>depth[y]) swap(x,y);
			ans+=a.query(New[x],New[y]),ans%=p;
			cout<<ans%p<<endl;
		}
		if(op==3)
		{
			cin>>z;z%=p;
			a.update(in[x],out[x],z);
		}
		if(op==4)
		{
			cout<<a.query(in[x],out[x])%p<<endl;
		}
	}
}