RE on #8,#9,#10

应该不是数组的问题。我已经开到1e7了（

#include<bits/stdc++.h>
using namespace std;
int n,q,rt,mod,a[10000005];
struct SegTree{
	int l,r,sum;
}tree[20000005];
int lazy[20000005];
struct node{
	int to,nxt,val;
}w[20000005];
int h[20000005],cnt=0;
void Link(int x,int y){
	++cnt;
	w[cnt].to=y;
	w[cnt].nxt=h[x];
	h[x]=cnt;
	return ;
}
int f[10000005],siz[10000005],dep[10000005];
int son[10000005],top[10000005];
int id[10000005],rk[10000005],tot=0;
void firdfs(int x,int fa){
	f[x]=fa; siz[x]=1; dep[x]=dep[fa]+1;
	for(int i=h[x];i!=0;i=w[i].nxt){
		int y=w[i].to;
		if(y==fa) continue;
		firdfs(y,x);
		siz[x]+=siz[y];
		if(siz[y]>siz[son[x]]) son[x]=y;
	}
	return ;
}
void secdfs(int x,int tp){
	top[x]=tp; id[x]=++tot; rk[tot]=x;
	if(!son[x]) return ;
	secdfs(son[x],tp);
	for(int i=h[x];i!=0;i=w[i].nxt){
		int y=w[i].to;
		if(y==son[x]) continue;
		if(y==f[x]) continue;
		secdfs(y,y);
	}
	return ;
}
void pushup(int p){
	tree[p].sum=(tree[p<<1].sum+tree[p<<1|1].sum)%mod;
	return ;
}
void pushdown(int p){
	if(lazy[p]){
		tree[p<<1].sum=(tree[p<<1].sum+lazy[p]*(tree[p<<1].r-tree[p<<1].l+1)%mod)%mod;
		tree[p<<1|1].sum=(tree[p<<1|1].sum+lazy[p]*(tree[p<<1|1].r-tree[p<<1|1].l+1)%mod)%mod;
		lazy[p<<1]=(lazy[p<<1]+lazy[p])%mod; lazy[p<<1|1]=(lazy[p<<1|1]+lazy[p])%mod;
		lazy[p]=0;
	}
	return ;
}
void build(int p,int l,int r){
	tree[p].l=l; tree[p].r=r;
	lazy[p]=0; tree[p].sum=a[rk[l]]%mod;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	pushup(p);
	return ;
}
void update(int p,int l,int r,int val){
	if(l<=tree[p].l&&tree[p].r<=r){
		tree[p].sum=(tree[p].sum+val*(tree[p].r-tree[p].l+1)%mod)%mod;
		lazy[p]=(lazy[p]+val)%mod;
		return ;
	}
	pushdown(p);
	int mid=(tree[p].l+tree[p].r)>>1;
	if(l<=mid) update(p<<1,l,r,val);
	if(r>mid) update(p<<1|1,l,r,val);
	pushup(p);
	return ;
}
int query(int p,int l,int r){
	if(l<=tree[p].l&&tree[p].r<=r) return tree[p].sum;
	pushdown(p);
	int qans=0,mid=(tree[p].l+tree[p].r)>>1;
	if(l<=mid) qans=(qans+query(p<<1,l,r)%mod)%mod;
	if(r>mid) qans=(qans+query(p<<1|1,l,r)%mod)%mod;
	return qans;
}
void update0(int x,int y,int val){
	int tx=top[x],ty=top[y];
	while(tx!=ty){
		if(dep[tx]>=dep[ty]){
			update(rt,id[tx],id[x],val);
			x=f[tx]; tx=top[x];
		}else{
			update(rt,id[ty],id[y],val);
			y=f[ty]; ty=top[y];
		}
	}
	if(id[x]<=id[y]) update(rt,id[x],id[y],val);
	else update(rt,id[y],id[x],val);
	return ;
}
int query0(int x,int y){
	int qans=0;
	int tx=top[x],ty=top[y];
	while(tx!=ty){
		if(dep[tx]>=dep[ty]){
			qans=(qans+query(rt,id[tx],id[x])%mod)%mod;
			x=f[tx]; tx=top[x];
		}else{
			qans=(qans+query(rt,id[ty],id[y])%mod)%mod;
			y=f[ty]; ty=top[y];
		}
	}
	if(id[x]<=id[y]) qans=(qans+query(rt,id[x],id[y])%mod)%mod;
	else qans=(qans+query(rt,id[y],id[x])%mod)%mod;
	return qans;
}
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
signed main(){
	n=read(); q=read(); rt=read(); mod=read();
	for(int i=1;i<=n;i++) a[i]=read(); 
	for(int i=1;i<n;i++){
		int u,v;
		u=read(); v=read();
		Link(u,v);
		Link(v,u);
	}
	firdfs(rt,0); 
	secdfs(rt,rt);
	build(rt,1,n);
	while(q--){
		int op=read();
		if(op==1){
			int x,y,val;
			x=read(); y=read();
			val=read();
			update0(x,y,val);
		}
		if(op==2){
			int x,y;
			x=read(); y=read();
			printf("%lld\n",query0(x,y));
		}
		if(op==3){
			int x,val;
			x=read(); val=read();
			update(rt,id[x],id[x]+siz[x]-1,val);
		}
		if(op==4){
			int x=read();
			printf("%lld\n",query(rt,id[x],id[x]+siz[x]-1));
		}
	}
	return 0;
}