RE on #9 求调

#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
#define maxn 1000001
#define lp p<<1
#define rp p<<1|1
using namespace std;
vector<int>e[maxn];
int n,m,st,mod,cnt,val[maxn],top[maxn],fa[maxn],son[maxn],dep[maxn],size[maxn],mygo[maxn],back[maxn],d[maxn<<2],lz[maxn<<2];
void add(int u,int v){
	e[u].push_back(v);
}
void dfs1(int p,int father){
	size[p]=1;
	fa[p]=father;
	dep[p]=dep[father]+1;
	for(auto q:e[p]){
		if(q==father) continue;
		fa[q]=p;
		dfs1(q,p);
		size[p]+=size[q];
		size[p]%=mod;
		if(size[q]>size[son[p]]) son[p]=q;
	}
}
void dfs2(int p){
	cnt++;
	mygo[p]=cnt;
	back[cnt]=val[p]%mod;
	for(auto q:e[p]){
		if(q==fa[p]) continue;
		if(q==son[p]) top[q]=top[p];
		else top[q]=q;
		dfs2(q);
	}
}
void build(int l,int r,int p){
	if(l==r){
		d[p]=back[l];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,lp);
	build(mid+1,r,rp);
	d[p]=d[lp]+d[rp];
	d[p]%=mod;
}
void push(int l,int r,int p,int k){
	d[p]+=(r-l+1)*k%mod;
	d[p]%=mod;
	lz[p]+=k;
	lz[p]%=mod;
}
void del(int l,int r,int p){
	if(lz[p]&&l!=r){
		int mid=l+r>>1;
		push(l,mid,lp,lz[p]);
		push(mid+1,r,rp,lz[p]);
		lz[p]=0;
	}
}
void add(int s,int t,int l,int r,int p,int k){
	if(s<=l&&r<=t){
		push(l,r,p,k);
		return;
	}
	int mid=l+r>>1;
	del(l,r,p);
	if(s<=mid) add(s,t,l,mid,lp,k);
	if(t>mid)  add(s,t,mid+1,r,rp,k);
	d[p]=d[lp]+d[rp];
	d[p]%=mod;
}
int get(int s,int t,int l,int r,int p){
	if(s<=l&&r<=t) return d[p]%mod;
	int mid=l+r>>1;
	del(l,r,p);
	int sum=0;
	if(s<=mid) sum+=get(s,t,l,mid,lp);
	if(t>mid)  sum+=get(s,t,mid+1,r,rp);
	return sum%mod;
}
void tree_add(int u,int v,int w){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		add(mygo[top[u]],mygo[u],1,n,1,w);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	add(mygo[u],mygo[v],1,n,1,w);
}
int tree_sum(int u,int v){
	int sum=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		sum+=get(mygo[top[u]],mygo[u],1,n,1);
		sum%=mod;
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	sum+=get(mygo[u],mygo[v],1,n,1);
	sum%=mod;
	return sum;
}
void node_add(int u,int w){
	add(mygo[u],mygo[u]+size[u]-1,1,n,1,w);
}
int node_sum(int u){
	return get(mygo[u],mygo[u]+size[u]-1,1,n,1);
}
signed main(){
	ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	int i,op,u,v,w;
	cin>>n>>m>>st>>mod;
	for(i=1;i<=n;i++) cin>>val[i];
	for(i=1;i<n;i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	dfs1(st,st);
	dfs2(st);
	build(1,n,1);
	for(i=1;i<=m;i++){
		cin>>op;
		switch(op){
			case(1):{
				cin>>u>>v>>w;
				tree_add(u,v,w%mod);
				break;
			}
			case(2):{
				cin>>u>>v;
				cout<<tree_sum(u,v)<<"\n";
				break;
			}
			case(3):{
				cin>>u>>w;
				node_add(u,w%mod);
				break;
			}
			case(4):{
				cin>>u;
				cout<<node_sum(u)<<"\n";
				break;
			}
		}
	}
}