【模板】线段树+树链

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=4e5+1000,INF=0x3f3f3f3f;
int n,m,a[maxn],lazy[maxn],root,mol,cnt,tot,dfn[maxn],size[maxn],rk[maxn],depth[maxn],son[maxn],par[maxn],head[maxn],top[maxn];
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;ch=getchar();
	}
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
	return s*w;
}
struct Edge{
	int next,to;
}e[maxn];
struct Node{
	int lazy,l,r,size,w;
}tree[maxn];
void Add(int x,int y){
	e[++tot].next=head[x];
	e[tot].to=y;
	head[x]=tot;
}
void DFS1(int u,int fa){
	par[u]=fa;
	size[u]=1;
	for(int x=head[u];x;x=e[x].next){
		int v=e[x].to;
		if(v==fa)continue;
		depth[v]=depth[u]+1;
		DFS1(v,u);
		size[u]+=size[v];
		if(!son[u]||size[son[u]]<size[v])son[u]=v;
	}
}//树剖第一个预处理，处理出par,size,son,depth
void DFS2(int u,int t){
	top[u]=t;
	dfn[u]=++cnt;
	rk[cnt]=a[u];
	if(son[u])DFS2(son[u],t);
	for(int x=head[u];x;x=e[x].next){
		int v=e[x].to;
		if(v!=par[u]&&v!=son[u])DFS2(v,v);
	}
}//树剖第二个预处理，处理处top,dfn,rk，其中dfn是树的新点，rk是新点的数
void pushup(int rt){
	tree[rt].w=(tree[rt*2].w+tree[rt*2+1].w+mol)%mol;
}//线段树开始
void Build(int rt,int l,int r){
	tree[rt].l=l;tree[rt].r=r;tree[rt].size=r-l+1;
	if(l==r){
		tree[rt].w=rk[l];//因为要构建新树的线段树，所以是rk
		return;
	}
	int mid=(l+r)/2;
	Build(rt*2,l,mid);
	Build(rt*2+1,mid+1,r);
	pushup(rt);
}//线段树构建
void update(int rt,int w){
	tree[rt].w=(tree[rt].w+tree[rt].size*w)%mol;
	tree[rt].lazy=(tree[rt].lazy+w)%mol;
}//下传lazy
void pushdown(int rt){
	update(rt*2,tree[rt].lazy);
	update(rt*2+1,tree[rt].lazy);
	tree[rt].lazy=0;
}//下传lazy
void modify(int rt,int s,int t,int w){
	if(s<=tree[rt].l&&t>=tree[rt].r){
		update(rt,w);
		return;
	}
	int l=tree[rt].l,r=tree[rt].r;
	pushdown(rt);
	int mid=(l+r)/2;
	if(s<=mid)modify(rt*2,s,t,w);
	if(t>mid)modify(rt*2+1,s,t,w);
	pushup(rt);
}
int query(int rt,int s,int t){
	if(s<=tree[rt].l&&t>=tree[rt].r)return tree[rt].w;
	pushdown(rt);
	int ans=0;
	int mid=(tree[rt].l+tree[rt].r)/2;
	if(s<=mid)ans=(ans+query(rt*2,s,t))%mol;
	if(t>mid)ans=(ans+query(rt*2+1,s,t))%mol;
	return ans;
}
void treeadd(int u,int v,int w){
	while(top[u]!=top[v]){
		if(depth[top[u]]<depth[top[v]])swap(u,v);
		modify(1,dfn[top[u]],dfn[u],w);		
		u=par[top[u]];
	}
	if(depth[u]>depth[v])swap(u,v);
	modify(1,dfn[u],dfn[v],w);
}
void sum(int u,int v){
	int ans=0;
	while(top[u]!=top[v]){
		if(depth[top[u]]<depth[top[v]])swap(u,v);
		ans=(ans+query(1,dfn[top[u]],dfn[u]))%mol;
		u=par[top[u]];
	}
	if(depth[u]>depth[v])swap(u,v);
	ans=(ans+query(1,dfn[u],dfn[v]))%mol;
	cout<<ans<<endl;
}
int main(){
	freopen("a.in","r",stdin);
	n=read(),m=read(),root=read(),mol=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		Add(x,y);Add(y,x);
	}
	DFS1(root,0);
	DFS2(root,root);
	Build(1,1,n);
	for(int i=1;i<=m;i++){
		int p=read();
		if(p==1){
			int x=read(),y=read(),z=read();
			treeadd(x,y,z%mol);
		}else if(p==2){
			int x=read(),y=read();
			sum(x,y);
		}else if(p==3){
			int x=read(),y=read();
			modify(1,dfn[x],dfn[x]+size[x]-1,y%mol);
		}else if(p==4){
			int x=read();
			cout<<query(1,dfn[x],dfn[x]+size[x]-1)%mol<<endl;
		}
		
	}
}