样例没过，10分，求条

记录

//#P661. ¡¾Ä£°å¡¿ÖØÁ´ÆÊ·Ö/Ê÷Á´ÆÊ·Ö
#include <bits/stdc++.h>
//#define int long long
using namespace std;
int mod;
namespace zmx{
	int modnum(int x){
		return (x+mod)%mod;
	}
	int qpow(int x,int y){
		int res=1;
		while(y){
			if(y&1){
				res=modnum(res*x);
			}
			x=modnum(x*x);
			y>>=1;
		}
	}
	
}
using namespace zmx;
struct Treearr{
private:
	int tr[1000005];//you can resize it
	int lowbit(int x){
		return x&(-x);
	}
	
public:
	int n;
	void resize(int x){
		n=x;
		for(int i=0;i<=n;i++){
			tr[x]=0;
		}
	}
	void upd(int x,int v){
		for(;x<=n;x+=lowbit(x)){
			tr[x]+=v;
			tr[x]=modnum(tr[x]);
		}
	}			
	int qry(int x){
		int res=0;
		for(;x;x-=lowbit(x)){
			res+=tr[x];
			res=modnum(res);
		}
		res=modnum(res);
		return res;
	}
}; 
int sum[1000005];
int a[1000005];
Treearr at,iat;
void init(int n){
	sum[0]=0;
	for(int i=1;i<=n;i++){
		sum[i]=0;
		sum[i]=sum[i-1]+a[i];
		sum[i]=modnum(sum[i]);
	}
	at.resize(n);
	iat.resize(n);
}
void update(int l,int r,int v){
	at.upd(l,v);
	at.upd(r+1,-v);
	iat.upd(l,l*v);
	iat.upd(r+1,-(r+1)*v);
}
int query(int l,int r){
	int ans=sum[r]-sum[l-1];
	ans+=(r+1)*at.qry(r)-iat.qry(r);
	ans=modnum(ans);
	ans-=l*at.qry(l-1)-iat.qry(l-1);
	ans=modnum(ans);
	return ans;
}
vector<int> g[1000005];
int fa[1000005];
int dep[1000005];
int siz[1000005];
int heavyson[1000005];
int top[1000005];
int dfn[1000005],dfncnt=0;
int to[1000005];
void dfs1(int u,int father){
	siz[u]=1;
	fa[u]=father;
	dep[u]=dep[father]+1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==father){
			continue;
		}
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[heavyson[u]]){
			heavyson[u]=v;
		}
	}
}
void dfs2(int u,int topnode){
	dfn[u]=++dfncnt;
	to[dfncnt]=u;
	top[u]=topnode;
	if(heavyson[u]){
		dfs2(heavyson[u],topnode);
	}
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa[u]){
			continue;
		}
		if(v==heavyson[u]){
			continue;
		}
		dfs2(v,v);
	}
}
void lcaadd(int u,int v,int w){
	w=modnum(w);
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]){
			swap(u,v);
		}
		update(dfn[top[u]],dfn[u],w);
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]){
		swap(u,v);
	}
	update(dfn[v],dfn[u],w);
	return;
}
int lcasum(int u,int v){
	int res=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]){
			swap(u,v);
		}
		res+=query(dfn[top[u]],dfn[u]);
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]){
		swap(u,v);
	}
	res+=query(dfn[v],dfn[u]);
	res=modnum(res);
	return res;
}
void addtree(int u,int w){
	w=modnum(w);
	int dfnu=dfn[u];
	int dfnallnode=dfn[u]+siz[u]-1;
	update(dfnu,dfnallnode,w);
	return;
}
int sumtree(int u){
	int dfnu=dfn[u];
	int dfnallnode=dfn[u]+siz[u]-1;
	return modnum(query(dfnu,dfnallnode));
}
int n,m,r,p;
void read(){
	cin>>n>>m>>r>>p;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	return;
}
void initwork(){
	mod=p;
	init(n);
	dfs1(r,r);
	dfs2(r,r);
	return;
}
void querywork(){
	while(m--){
		int op;
		cin>>op;
		if(op==1){
			int x,y,z;
			cin>>x>>y>>z;
			lcaadd(x,y,z);
		}else if(op==2){
			int x,y;
			cin>>x>>y;
			cout<<modnum(lcasum(x,y))<<endl;
		}else if(op==3){
			int x,z;
			cin>>x>>z;
			addtree(x,z);	
		}else{
			int x;
			cin>>x;
			cout<<modnum(sumtree(x))<<endl;
		}
	}
	return;
}
int main(){
	read();
	initwork();
	querywork();
	return 0;
}