rt，重儿子换成第一个儿子然后过了，跑得比重链剖分还快。

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=4e5+10;

int n,m,r,p;
int a[N];
int an[N];
int deep[N];
int siz[N];
int fa[N];
int son[N];
int id[N];
int cnt;
int top[N];
int tree[N];
int lazy[N];
int res;

vector<int>v[N];

void dfs1(int x,int f,int de){
	deep[x]=de;
	fa[x]=f;
	siz[x]=1;
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i];
		if(y==f) continue;
		dfs1(y,x,de+1);
		siz[x]+=siz[y];
		if(!son[x]){
			son[x]=y;
		}
	}
}

void dfs2(int x,int topfa){
	id[x]=++cnt;
	an[cnt]=a[x];
	top[x]=topfa;
	
	if(!son[x]) return;
	dfs2(son[x],topfa);
	
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i];
		if(y==fa[x]||y==son[x]) continue;
		dfs2(y,y);
	}
}

void build(int rt,int l,int r){
	if(l==r){
		tree[rt]=an[l];
		tree[rt]%=p;
		return;
	}
	int mid=(l+r)/2;
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
	tree[rt]=(tree[rt*2]+tree[rt*2+1])%p;
}

void pushdown(int rt,int len){
	lazy[rt*2]+=lazy[rt];
	lazy[rt*2+1]+=lazy[rt];
	tree[rt*2]+=lazy[rt]*(len-len/2);
	tree[rt*2+1]+=lazy[rt]*(len/2);
	tree[rt*2]%=p;
	tree[rt*2+1]%=p;
	lazy[rt]=0;
}

void update(int rt,int l,int r,int L,int R,int k){
	if(L<=l&&r<=R){
		lazy[rt]+=k;
		tree[rt]+=k*(r-l+1);
		return;
	}
	if(lazy[rt]) pushdown(rt,r-l+1);
	int mid=(l+r)/2;
	if(L<=mid) update(rt*2,l,mid,L,R,k);
	if(R>mid) update(rt*2+1,mid+1,r,L,R,k);
	tree[rt]=(tree[rt*2]+tree[rt*2+1])%p;
}

void query(int rt,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		res+=tree[rt];
		res%=p;
		return;
	}
	if(lazy[rt]) pushdown(rt,r-l+1);
	int mid=(l+r)/2;
	if(L<=mid) query(rt*2,l,mid,L,R);
	if(R>mid) query(rt*2+1,mid+1,r,L,R);
}

void updateL(int x,int y,int z){
	z%=p;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]]){
			swap(x,y);
		}
		update(1,1,n,id[top[x]],id[x],z);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	update(1,1,n,id[x],id[y],z);
}

int queryL(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]]){
			swap(x,y);
		}
		res=0;
		query(1,1,n,id[top[x]],id[x]);
		ans+=res;
		ans%=p;
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	res=0;
	query(1,1,n,id[x],id[y]);
	ans+=res;
	return ans%p;
}

void updateS(int x,int z){
	update(1,1,n,id[x],id[x]+siz[x]-1,z);
}

int queryS(int x){
	res=0;
	query(1,1,n,id[x],id[x]+siz[x]-1);
	return res%p;
}

int main(){
	scanf("%d%d%d%d",&n,&m,&r,&p);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n-1;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs1(r,0,1);
	dfs2(r,r);
	build(1,1,n);
	while(m--){
		int op,x,y,z;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%d",&x,&y,&z);
			updateL(x,y,z);
		}
		if(op==2){
			scanf("%d%d",&x,&y);
			printf("%d\n",queryL(x,y));
		}
		if(op==3){
			scanf("%d%d",&x,&z);
			updateS(x,z);
		}
		if(op==4){
			scanf("%d",&x);
			printf("%d\n",queryS(x));
		}
	}
	return 0;
}