提交记录https://www.luogu.com.cn/record/169112807

#3#11AC（大概是运气过的），#8#9#10MLE，其余WA

代码如下：

#include<bits/stdc++.h>
#define int long long
#define for(i,x,y) for(register int i=x;i<=y;i++)
using namespace std;
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int N=1e5+5;
int n,m,root,mod,opt;
int u,v,cnt,head[N];
int cnt_val[N],ans,res;
struct POINT{
	int id,val,dep,top,fa,heavy_son,size;
}a[N];
struct EDGE{
	int next;
	int to;
}edge[N];
struct node{
	int val;
	int lazy;
}b[N<<2];
void add(int x,int y){
	cnt++;
	edge[cnt]={head[x],y};
	head[x]=cnt;
}
void dfs_1(int x,int father,int depth){
	a[x].dep=depth;
	a[x].fa=father;
	a[x].size=1;
	int maxson=-1;
	int i=head[x];
	while(i){
		int y=edge[i].to;
		if(y==father);
		else{
			dfs_1(y,x,depth+1);
			a[x].size+=a[y].size;
			if(a[y].size>maxson){
				a[x].heavy_son=y;
				maxson=a[y].size;
			}
		}
		i=edge[i].next;
	}
}
void dfs_2(int x,int top){
	cnt++;
	a[x].id=cnt;
	cnt_val[cnt]=a[x].val;
	a[x].top=top;
	if(a[x].heavy_son==0)return;
	dfs_2(a[x].heavy_son,top);
	int i=head[x];
	while(i){
		int y=edge[i].to;
		if(y==a[x].fa||y==a[x].heavy_son);
		else dfs_2(y,y);
		i=edge[i].next;
	}
}
void build_the_tree(int rt,int l,int r){
	if(l==r){
		b[rt].val=cnt_val[l]%mod;
		return;
	}
	int mid=(l+r)>>1;
	build_the_tree(rt*2,l,mid);
	build_the_tree(rt*2+1,mid+1,r);
	b[rt].val=(b[rt*2].val+b[rt*2+1].val)%mod;
}
void pass_the_tree(int rt,int l,int r){
	int mid=(l+r)>>1;
	b[rt*2].lazy=b[rt].lazy;
	b[rt*2].val=(b[rt*2].val+b[rt*2].lazy*(mid-l+1)%mod)%mod;
	b[rt*2+1].lazy=b[rt].lazy;
	b[rt*2+1].val=(b[rt*2+1].val+b[rt*2+1].lazy*(r-mid)%mod)%mod;
	b[rt].lazy=0;
}
void change_the_tree(int rt,int l,int r,int l_should,int r_should,int k){
	if(l>r_should||r<l_should)return;
	else if(l>=l_should&&r<=r_should){
		b[rt].lazy+=k;
		b[rt].val+=k*(r-l+1);
		return;
	}
	else{
		pass_the_tree(rt,l,r);
		int mid=(l+r)>>1;
		change_the_tree(rt*2,l,mid,l_should,r_should,k);
		change_the_tree(rt*2+1,mid+1,r,l_should,r_should,k);
		b[rt].val=(b[rt*2].val+b[rt*2+1].val)%mod;
	}
}
void print_the_tree(int rt,int l,int r,int l_should,int r_should){
	if(l>r_should||r<l_should)return;
	else if(l>=l_should&&r<=r_should){
		res=(res+b[rt].val)%mod;
		return;
	}
	else{
		pass_the_tree(rt,l,r);
		int mid=(l+r)>>1;
		print_the_tree(rt*2,l,mid,l_should,r_should);
		print_the_tree(rt*2+1,mid+1,r,l_should,r_should);
	}
}
signed main(){
	n=read(),m=read(),root=read(),mod=read();
	for(i,1,n)a[i].val=read();
	for(i,1,n-1){
		u=read(),v=read();
		add(u,v);
		add(v,u);
	}
	dfs_1(root,0,1);
	cnt=0;
	dfs_2(root,root);
	build_the_tree(1,1,n);
	for(i,1,m){
		opt=read();
		int x,y,z,temp;
		switch(opt){
			case 1:
				x=read(),y=read(),z=read();
				z%=mod;
				while(a[x].top!=a[y].top){
					if(a[a[x].top].dep<a[a[y].top].dep)temp=x,x=y,y=temp;
					change_the_tree(1,1,n,a[a[x].top].id,a[x].id,z);
					x=a[a[x].top].fa;
				}
				if(a[x].dep>a[y].dep)temp=x,x=y,y=temp;
				change_the_tree(1,1,n,a[x].id,a[y].id,z);
				break;
			case 2:
				x=read(),y=read();
				ans=0;
				while(a[x].top!=a[y].top){
					if(a[a[x].top].dep<a[a[y].top].dep)temp=x,x=y,y=temp;
					res=0;
					print_the_tree(1,1,n,a[a[x].top].id,a[x].id);
					ans=(ans+res)%mod;
					x=a[a[x].top].fa;
				}
				if(a[x].dep>a[y].dep)temp=x,x=y,y=temp;
				res=0;
				print_the_tree(1,1,n,a[x].id,a[y].id);
				ans=(ans+res)%mod;
				printf("%lld\n",ans);
				break;
			case 3:
				x=read(),z=read();
				change_the_tree(1,1,n,a[x].id,a[x].id+a[x].size-1,z);
				break;
			case 4:
				x=read();
				res=0;
				print_the_tree(1,1,n,a[x].id,a[x].id+a[x].size-1);
				printf("%lld\n",res%mod);
				break;
		}
	}
	return 0;
}