10pts 只过最后一个点 求条悬关

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,mod,r;
struct node{
	int add,sum;
}tr[400000];
int a[400010];
struct node1{
	int to,nxt;
}e[400010];
int head[400010],cnt;
int w[400010],wt[400010],siz[400010],top[400010],dep[400010],fa[400010],id[400010],son[400010];
int res=0,ans;
int cnt1;
void add(int x,int y){
	e[++cnt1].to=y;
	e[cnt1].nxt=head[x];
	head[x]=cnt1;
}
void pushup(int cnt){
	tr[cnt].sum=(tr[cnt*2].sum+tr[cnt*2+1].sum)%mod;
}
void build(int cnt,int l,int r){
	int mid=(l+r)/2;
	if(l==r){
		tr[cnt].sum=w[id[l]];
		return ;
	}
	build(cnt*2,l,mid);
	build(cnt*2+1,mid+1,r);
	pushup(cnt);
}
void pushdown(int cnt,int l,int r){
	int mid=(l+r)/2;
	tr[cnt*2].add+=tr[cnt].add;
	tr[cnt*2+1].add+=tr[cnt].add;
	tr[cnt*2].sum=(tr[cnt*2].sum+(mid-l+1)*tr[cnt].add)%mod;
	tr[cnt*2+1].sum=(tr[cnt*2+1].sum+(r-mid)*tr[cnt].add)%mod;
	tr[cnt].add=0;
}
void modify(int cnt,int l,int r,int ql,int qr,int k){
	int mid=(l+r)/2;//printf("add [%d,%d]\n",l,r);
	if(ql>r||qr<l) return ;
	
	if(ql<=l&&r<=qr){
		tr[cnt].sum=(tr[cnt].sum+(r-l+1)*k)%mod;
		tr[cnt].add+=k;
		return ;
	}
	pushdown(cnt,l,r);
	modify(cnt*2,l,mid,ql,qr,k);
	modify(cnt*2+1,mid+1,r,ql,qr,k);
	pushup(cnt);
	return ;
}
int query(int cnt,int l,int r,int ql,int qr){
	int mid=(l+r)/2;
	if(ql>r||qr<l) return 0;
	if(ql<=l&&r<=qr){
		return tr[cnt].sum%mod;
	}
	pushdown(cnt,l,r);
	return (query(cnt*2,l,mid,ql,qr)+query(cnt*2+1,mid+1,r,ql,qr))%mod;
}
inline int qrange(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans+=query(1,1,n,id[top[x]],id[x]);
		ans%=mod;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans+=query(1,1,n,id[x],id[y]);
	ans%=mod;
	return ans;
}
inline void updrange(int x,int y,int k){
	k%=mod;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		modify(1,1,n,id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	modify(1,1,n,id[x],id[y],k);
}
inline int qson(int x){
	return query(1,1,n,id[x],id[x]+siz[x]-1)%mod;
}
inline void updson(int x,int k){
	modify(1,1,n,id[x],id[x]+siz[x]-1,k);
}
inline void dfs1(int x,int f,int deep){
	//printf("%d\n",x);
	dep[x]=deep;
	fa[x]=f;
	siz[x]=1;
	int maxson=-1;
	for (int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==f) continue;
		dfs1(y,x,deep+1);
		siz[x]+=siz[y];
		if(siz[y]>maxson) son[x]=y,maxson=siz[y];
	}
}
inline void dfs2(int x,int topf){
	id[x]=++cnt;
	wt[cnt]=w[x];
	top[x]=topf;
	if(!son[x]) return ;
	dfs2(son[x],topf);
	for (int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==fa[x]||y==son[x]) continue;
		dfs2(y,y);
	}
}
signed main(){
	cin>>n>>m>>r>>mod;
	for (int i=1;i<=n;i++) cin>>w[i];
	for (int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		add(a,b),add(b,a);
	}
	dfs1(r,0,1);
	dfs2(r,r);
	build(1,1,n);
	//modify(1,1,n,1,n,1);
	//cout<<query(1,1,n,1,3);
	/*cout<<endl;
	for (int i=1;i<=n;i++)
	cout<<dep[i]<<' ';
	cout<<endl;*/
	//for(int i=1;i<=n;i++) printf("id[%d], is %d\n",i,id[i]);
	while(m--){
		int k,x,y,z;
		cin>>k;
		if(k==1){
			cin>>x>>y>>z;
			updrange(x,y,z);
		}
		else if(k==2){
			cin>>x>>y;
			cout<<qrange(x,y)%mod<<endl;
		}
		else if(k==3){
			cin>>x>>y;
			updson(x,y);
		}
		else{
			cin>>x;
			cout<<qson(x)%mod<<endl;
		}
		//for(int i=1;i<=n;i++) printf("%d ",query(1,1,n,id[i],id[i]));
		//putchar('\n');
	}
	return 0;
}