```cpp
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0' or ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' and ch<='9')s=s*10+(ch-'0'),ch=getchar();
return s*w;
}
inline ll read_ll()
{
ll s=0,w=1;
char ch=getchar();
while(ch<'0' or ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' and ch<='9')s=s*10+(ch-'0'),ch=getchar();
return s*w;
}
const int MAXN(1e5+10);
int n,m,rt;
ll mod,a[MAXN],b[MAXN];
struct E{int to,nxt;};
E edge[MAXN<<1];
int head[MAXN],tot,cnt;
int idx[MAXN],rk[MAXN],top[MAXN],par[MAXN],son[MAXN],dep[MAXN],siz[MAXN];
inline void Swap(int&x,int&y){x^=y;y^=x;x^=y;}
//idx[u] u在序列的位置
//rk[u] dfs序为 u 的节点编号
inline void add_edge(int u,int v)
{
edge[++tot].nxt=head[u];
head[u]=tot;
edge[tot].to=v;
return;
}
struct Segment
{
ll tree[MAXN*4],tag[MAXN*4];
inline int lc(int p){return p<<1;}
inline int rc(int p){return p<<1|1;}
inline void push_up(int u){tree[u]=(tree[lc(u)]+tree[rc(u)])%mod;return;}
inline void lazy_tag(int u,int l,int r,ll k)
{
tag[u]=(tag[u]+k)%mod;
tree[u]=(tree[u]+k*(r-l+1))%mod;
return;
}
inline void push_down(int u,int l,int r)
{
int mid=(l+r)>>1;
lazy_tag(lc(u),l,mid,tag[u]);
lazy_tag(rc(u),mid+1,r,tag[u]);
tag[u]=0;
return;
}
inline void build(int u,int l,int r)
{
if(l==r)
{
tree[u]=a[rk[l]];
return;
}
int mid=(l+r)>>1;
build(lc(u),l,mid);
build(rc(u),mid+1,r);
push_up(u);
return;
}
inline void update(int u,int l,int r,int ln,int rn,ll k)
{
if(ln<=l&&r<=rn)
{
lazy_tag(u,l,r,k);
return;
}
push_down(u,l,r);
int mid=(l+r)>>1;
if(ln<=mid) update(lc(u),l,mid,ln,rn,k);
if(rn>mid) update(rc(u),mid+1,r,ln,rn,k);
push_up(u);
return;
}
inline ll query(int u,int l,int r,int ln,int rn)
{
ll res(0);
if(ln<=l&&r<=rn) return tree[u]%mod;
push_down(u,l,r);
int mid=(l+r)>>1;
if(ln<=mid) res=(res+query(lc(u),l,mid,ln,rn))%mod;
if(rn>mid) res=(res+query(rc(u),mid+1,r,ln,rn))%mod;
return res;
}
};
Segment Tree;
inline void dfs1(int u,int fa,int depth)
{
siz[u]=1;
dep[u]=depth;
par[u]=fa;
for(register int i=head[u];i;i=edge[i].nxt)
{
E e=edge[i];
if(e.to==fa) continue;
dfs1(e.to,u,depth+1);
siz[u]+=siz[e.to];
if(siz[e.to]>siz[son[u]]) son[u]=e.to;
}
return;
}
inline void dfs2(int u,int topf)
{
top[u]=topf;
idx[u]=++cnt;
rk[cnt]=u;
if(!son[u]) return;//叶子节点没有重儿子
dfs2(son[u],topf);
for(register int i=head[u];i;i=edge[i].nxt)
{
E e=edge[i];
if(e.to==par[u]||e.to==son[u]) continue;
dfs2(e.to,e.to);
}
return;
}
inline ll sum(int x,int y)
{
int fx=top[x],fy=top[y];
ll res(0);
while(fx!=fy)
{
if(dep[fx]>=dep[fy])
{
res=(res+Tree.query(1,1,n,idx[fx],idx[x]))%mod;
x=par[fx];
fx=top[x];
}
else
{
res=(res+Tree.query(1,1,n,idx[fy],idx[y]))%mod;
y=par[fy];
fy=top[y];
}
}
if(idx[x]>idx[y]) Swap(x,y);
res=(res+Tree.query(1,1,n,idx[x],idx[y]))%mod;
return res;
}
inline void modify(int x,int y,ll k)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]>=dep[fy])
{
Tree.update(1,1,n,idx[fx],idx[x],k);
x=par[x];
fx=top[x];
}
else
{
Tree.update(1,1,n,idx[fy],idx[y],k);
y=par[y];
fy=top[y];
}
}
if(idx[x]>idx[y]) Swap(x,y);
Tree.update(1,1,n,idx[x],idx[y],k);
return;
}
inline void change(int u,ll k)
{
Tree.update(1,1,n,idx[u],idx[u]+siz[u]-1,k);
return;
}
inline int qson(int u){return Tree.query(1,1,n,idx[u],idx[u]+siz[u]-1);}
int main()
{
n=read(),m=read(),rt=read(),mod=read_ll();
for(register int i=1;i<=n;i++) a[i]=read_ll();
for(register int i=1;i<n;i++)
{
int u=read(),v=read();
add_edge(u,v);
add_edge(v,u);
}
dfs1(rt,0,1);
dfs2(rt,rt);
Tree.build(1,1,n);
while(m--)
{
int opt=read();
if(opt==1)
{
int x=read(),y=read();
ll z=read_ll()%mod;
modify(x,y,z);
}
else if(opt==2)
{
int x=read(),y=read();
printf("%lld\n",sum(x,y)%mod);
}
else if(opt==3)
{
int u=read();
ll k=read_ll()%mod;
change(u,k);
}
else
{
int u=read();
printf("%lld\n",qson(u)%mod);
}
}
return 0;
}
```
by UperFicial @ 2021-07-21 14:33:33
@[UperFicial](/user/360511) 这不是std吧（
by ByGones @ 2021-07-21 14:34:49
@[卞宇轩](/user/209848) 确实（
by UperFicial @ 2021-07-21 14:48:23
@[UperFicial](/user/360511) modify里面应该是 `x=par[fx]`， y 同理
实测能过了
by w23c3c3 @ 2021-07-21 15:28:11
@[UperFicial](/user/360511) 建议学习一下题解第一篇，特别简洁qwq，您这种写法感觉太冗杂了
by Durancer @ 2021-07-21 15:28:14
@[w23c3c3](/user/109942) 感谢
by UperFicial @ 2021-07-21 15:30:24
@[Chen_怡](/user/230804) ok
by UperFicial @ 2021-07-21 15:33:15
有钱人
by peterwuyihong @ 2021-07-21 15:34:30
立竿见影
by Evier @ 2021-07-21 19:32:33