P3384

RE #1~10,AC #11

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define fd(i,a,b) for(int i=(a);i<=(b);i=-~i)
#define bd(i,a,b) for(int i=(a);i>=(b);i=~-i)
#define db(x) cout<<"DEBUG "<<#x<<" = "<<x<<endl;
using namespace std;

const int N=2e5+509,M=5e5+509,Mod=998244353;

int n,m,mod,rp;
int val[N],v[N];
int son[N],fa[N],id[N],tot,dep[N],siz[N],top[N];
vector<int> e[N];

//--------------线段树-----------------

struct st
{
    int l,r,sum,add;
    #define ls(p) (p<<1)
    #define rs(p) (p<<1|1)
    #define sum(p) (t[p].sum)
    #define add(p) (t[p].add)
    #define len(p) (t[p].r-t[p].l+1)
}t[N<<1];

inline void pushup(int p)
{
    sum(p)=(sum(ls(p))+sum(rs(p)))%mod;
}

inline void pushdown(int p)
{
    if(!add(p)) return;
    (add(ls(p))+=add(p))%=mod;
    (add(rs(p))+=add(p))%=mod;
    (sum(ls(p))+=add(p)*len(ls(p))%mod)%=mod;
    (sum(rs(p))+=add(p)*len(rs(p))%mod)%=mod;
    add(p)=0;
}

#define mid(p) (((t[p].r-t[p].l)>>1)+t[p].l)
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r,add(p)=0,sum(p)=0;
    if(l==r) {sum(p)=val[l]%mod;return;}
    build(ls(p),l,mid(p));
    build(rs(p),mid(p)+1,r);
    pushup(p);
}

int ask(int p,int l,int r)
{
    if(l<=t[p].l&&t[p].r<=r) return sum(p);
    pushdown(p);
	int res=0;
    if(l<=mid(p)) res+=ask(ls(p),l,r)%mod;
    if(r>mid(p)) res+=ask(rs(p),l,r)%mod;
    pushup(p);
	return res%mod;
}

void change(int p,int l,int r,int k)
{
    if(l<=t[p].l&&t[p].r<=r)
    {
        (add(p)+=k)%=mod;
		(sum(p)+=k*len(p)%mod)%=mod;
		return;
    }
    pushdown(p);
    if(l<=mid(p)) change(ls(p),l,r,k);
    if(r>mid(p)) change(rs(p),l,r,k);
    pushup(p);
}

//---------------END------------------

//--------------树 剖-----------------

//找重儿子
void getson(int x,int fat,int d)
{
	dep[x]=d;fa[x]=fat;siz[x]=1;
	int maxx=-1;
	for(auto y:e[x])
	{
		if(y==fa[x]) continue;
		getson(y,x,d+1);
		siz[x]+=siz[y];
		if(siz[y]>maxx)
		{
			son[x]=y;
			maxx=siz[y];
		}
	}
}

//找链顶+dfs序
void gettop(int x,int tp)
{
	id[x]=++tot;val[id[x]]=v[x];top[x]=tp;
	if(!son[x]) return;gettop(son[x],tp);
	for(auto y:e[x])
	{
		if(y==fa[x]||y==son[x]) continue;
		gettop(y,y);
	}
}

//查询x~y路径和
inline int askR(int x,int y)
{
	int res=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		(res+=ask(1,id[top[x]],id[x]))%=mod;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	(res+=ask(1,id[x],id[y]))%=mod;
	return res%mod;
}

//修改x~y路径
inline int updR(int x,int y,int k)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		change(1,id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	change(1,id[x],id[y],k);
}

//查询x子树和
inline int askS(int x)
{
	return ask(1,id[x],id[x]+siz[x]-1);
}

//修改x子树和
inline void updS(int x,int k)
{
	change(1,id[x],id[x]+siz[x]-1,k);
}

//---------------END------------------

signed main()
{
// #define FJ
#ifdef FJ
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    // freopen("A.in","r",stdin);
    // freopen("A.out","w",stdout);
#endif
    
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	
    cin>>n>>m>>rp>>mod;
	fd(i,1,n) cin>>v[i];
	fd(i,1,n-1)
	{
		int x,y;cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	
	getson(rp,0,1);
	gettop(rp,rp);
	build(1,1,n);

	while(m--)
	{
		int k,x,y,z;
		cin>>k;
		if(k==1)
		{
			cin>>x>>y>>z;
			updR(x,y,z);
		}
		else if(k==2)
		{
			cin>>x>>y;
			cout<<askR(x,y)<<endl;
		}
		else if(k==3)
		{
			cin>>x>>y;
			updS(x,y);
		}
		else
		{
			cin>>x;
			cout<<askS(x)<<endl;
		}
	}

    return 0;
}