树链剖分+线段树

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
	int l,r,sum,lz;
};
vector<int> tree[N];
int n,m,s,x,y,r,p;
int fa[N],depth[N],son[N],sz[N],top[N],id[N],cnt,nw[N],w[N];
int cmd,t1,t2,t3;
node seg_tree[N<<2];
void biuld(int k,int l,int r){
	seg_tree[k].l=l,seg_tree[k].r=r;
	seg_tree[k].lz=0;
	if(l==r){
		seg_tree[k].sum=nw[l]%p;
		return;
	}
	int mid=l+r>>1;
	biuld(k*2,l,mid);
	biuld(k*2+1,mid+1,r);
	seg_tree[k].sum=(seg_tree[k<<1].sum+seg_tree[(k<<1)|1].sum)%p;
}
void push_down(int k){
	seg_tree[k<<1].lz+=seg_tree[k].lz;
	seg_tree[k<<1|1].lz+=seg_tree[k].lz;
	seg_tree[k<<1].sum+=seg_tree[k].lz*(seg_tree[k<<1].r-seg_tree[k<<1].l+1);
	seg_tree[k<<1|1].sum+=seg_tree[k].lz*(seg_tree[k<<1|1].r-seg_tree[k<<1|1].l+1);
	seg_tree[k<<1].sum%=p;
	seg_tree[k<<1|1].sum%=p;
	seg_tree[k].lz=0;
}
void add(int k,int l,int r,int val){
	if(seg_tree[k].l>=l&&seg_tree[k].r<=r){
		seg_tree[k].sum+=val*(seg_tree[k].r-seg_tree[k].l+1);
		seg_tree[k].lz+=val;
		return;
	}
	if(seg_tree[k].lz!=0) push_down(k);
	if(seg_tree[k<<1].r>=l) add(k<<1,l,r,val);
	if(seg_tree[k<<1|1].l<=r) add(k<<1|1,l,r,val);
	seg_tree[k].sum=(seg_tree[k<<1].sum+seg_tree[k<<1|1].sum)%p;
}
int query(int k,int l,int r){
	if(seg_tree[k].l>=l&&seg_tree[k].r<=r) return seg_tree[k].sum%p;
	if(seg_tree[k].lz!=0) push_down(k);
	int cnt=0;
	if(seg_tree[k<<1].r>=l) cnt+=query(k<<1,l,r);
	if(seg_tree[k<<1|1].l<=r) cnt+=query(k<<1|1,l,r);
	return cnt%p;
}
void dfs1(int t,int f){
	depth[t]=depth[f]+1;
	fa[t]=f;
	sz[t]=1;
	int tmp=0;
	for(int i=0;i<tree[t].size();i++){
		if(tree[t][i]==fa[t]) continue;
		dfs1(tree[t][i],t);
		sz[t]+=sz[tree[t][i]];
		if(sz[tree[t][i]]>tmp){
			tmp=sz[tree[t][i]];
			son[t]=tree[t][i];
		}
	}
}
void dfs2(int t,int f){
	id[t]=++cnt;
	nw[cnt]=w[t];
	top[t]=f;
	if(son[t]==0) return;
	dfs2(son[t],f);
	for(int i=0;i<tree[t].size();i++){
		int node=tree[t][i];
		if(node!=son[t]&&node!=fa[t]) dfs2(node,node);
	}
}
int query_path(int u,int v){
	int ans=0;
	while(top[u]!=top[v]){
		if(depth[top[u]]<depth[top[v]]) swap(u,v);
		ans+=query(1,id[top[u]],id[u]);
		ans%=p;
		u=fa[top[u]];
	}
	if(depth[u]>depth[v]) swap(u,v);
	return (ans+query(1,id[u],id[v]))%p;
}
void update_path(int u,int v,int z){
	z%=p;
	while(top[u]!=top[v]){
		if(depth[top[u]]<depth[top[v]]) swap(u,v);
		add(1,id[top[u]],id[u],z);
		u=fa[top[u]];
	}
	if(depth[u]>depth[v]) swap(u,v);
	add(1,id[u],id[v],z);
}
inline int query_son(int x){
	return query_path(id[x],id[x]+sz[x]-1)%p;
}
inline void update_son(int x,int z){
	update_path(id[x],id[x]+sz[x]-1,z);
}
int main(){
	scanf("%d%d%d%d",&n,&m,&r,&p);
	for(int i=1;i<=n;i++) scanf("%d",&w[i]);
	for(int i=1;i<n;i++) scanf("%d%d",&x,&y),tree[x].push_back(y),tree[y].push_back(x);
	dfs1(r,0);
	dfs2(r,r);
	biuld(1,1,n);
	while(m--){
		scanf("%d",&cmd);
		switch(cmd){
			case 1:
				scanf("%d%d%d",&t1,&t2,&t3);
				update_path(t1,t2,t3);
				break;
			case 2:
				scanf("%d%d",&t1,&t2);
				printf("%d\n",query_path(t1,t2));
				break;
			case 3:
				scanf("%d%d",&t1,&t2);
				update_son(t1,t2);
				break;
			case 4:
				scanf("%d",&t1);
				printf("%d\n",query_son(t1));
				break;
		}
	}
}