显然是一道模板题。
然而索引出现了错误，狂wa不止。
感谢神犇Dr_J指正。%%%orz。
建线段树的时候，第44行。
把sum[p]=bv[pos[l]]%mod;打成了sum[p]=bv[in[l]]%mod;
忘了要用反映射搞一下......
树链剖分，从每个节点的儿子中，找出子树最大的一个作为重儿子。
然后以此将树链分成轻链和重链。
之后dfs一遍求出树链剖分序。
树链剖分序不仅保证子树内节点的编号在序列上连续，还保证一条重链上的节点的编号连续。
用一个线段树维护一下。
更改/询问子树的时候就是区间修改/查询区间和。
更改/询问树链的时候就是一步一步跳重链，每次一个区间修改/查询区间和。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std; int n,m,root;
ll mod;
ll bv[];
int hd[],to[],nx[],ec;
int sz[],f[],d[];
int son[],tp[];
int in[],out[],pc,pos[];
int lb[],rb[];
ll sum[],lz[]; void edge(int af,int at)
{
to[++ec]=at;
nx[ec]=hd[af];
hd[af]=ec;
} void pushup(int p)
{
sum[p]=((sum[p<<]+sum[p<<|])%mod+mod)%mod;
} void pushdown(int p)
{
if(!lz[p])return;
sum[p<<]=((sum[p<<]+(rb[p<<]-lb[p<<]+)%mod*lz[p]%mod)%mod+mod)%mod;
sum[p<<|]=((sum[p<<|]+(rb[p<<|]-lb[p<<|]+)%mod*lz[p]%mod)%mod+mod)%mod;
lz[p<<]=((lz[p<<]+lz[p])%mod+mod)%mod;
lz[p<<|]=((lz[p<<|]+lz[p])%mod+mod)%mod;
lz[p]=;
} void build(int p,int l,int r)
{
lb[p]=l,rb[p]=r;
if(l==r)
{
sum[p]=bv[pos[l]]%mod;
return;
}
int mid=(l+r)>>;
build(p<<,l,mid);
build(p<<|,mid+,r);
pushup(p);
} void add(int p,int l,int r,ll v)
{
if(lb[p]>=l&&rb[p]<=r)
{
sum[p]=(sum[p]+(rb[p]-lb[p]+)%mod*v%mod)%mod;
lz[p]=(lz[p]+v)%mod;
return;
}
pushdown(p);
int mid=(lb[p]+rb[p])>>;
if(l<=mid)add(p<<,l,r,v);
if(r>mid)add(p<<|,l,r,v);
pushup(p);
} ll query(int p,int l,int r)
{
if(lb[p]>=l&&rb[p]<=r)return sum[p];
pushdown(p);
int mid=(lb[p]+rb[p])>>;
ll ret=;
if(l<=mid)ret=((ret+query(p<<,l,r))%mod+mod)%mod;
if(r>mid)ret=((ret+query(p<<|,l,r))%mod+mod)%mod;
return ret;
} void pre(int p,int fa)
{
d[p]=d[fa]+,f[p]=fa,sz[p]=;
for(int i=hd[p];i;i=nx[i])
{
if(to[i]==fa)continue;
pre(to[i],p);
sz[p]+=sz[to[i]];
if(sz[to[i]]>sz[son[p]])son[p]=to[i];
}
} void dfs(int p)
{
in[p]=++pc;
pos[pc]=p;
if(p==son[f[p]])tp[p]=tp[f[p]];
else tp[p]=p;
if(son[p])dfs(son[p]);
for(int i=hd[p];i;i=nx[i])
if(to[i]!=f[p]&&to[i]!=son[p])dfs(to[i]);
out[p]=pc;
} int main()
{
scanf("%d%d%d%lld",&n,&m,&root,&mod);
for(int i=;i<=n;i++)scanf("%lld",&bv[i]);
for(int i=;i<n;i++)
{
int ff,tt;
scanf("%d%d",&ff,&tt);
edge(ff,tt),edge(tt,ff);
}
pre(root,root);
dfs(root);
build(,,n);
for(int i=;i<=m;i++)
{
int op;
scanf("%d",&op);
if(op==)
{
int x,y;
ll z;
scanf("%d%d%lld",&x,&y,&z);
z%=mod;
while(tp[x]!=tp[y])
{
if(d[tp[x]]<d[tp[y]])swap(x,y);
add(,in[tp[x]],in[x],z);
x=f[tp[x]];
}
if(d[x]>d[y])swap(x,y);
add(,in[x],in[y],z);
}
if(op==)
{
int x,y;
scanf("%d%d",&x,&y);
ll ans=;
while(tp[x]!=tp[y])
{
if(d[tp[x]]<d[tp[y]])swap(x,y);
ans=((ans+query(,in[tp[x]],in[x]))%mod+mod)%mod;
x=f[tp[x]];
}
if(d[x]>d[y])swap(x,y);
ans=((ans+query(,in[x],in[y]))%mod+mod)%mod;
printf("%lld\n",ans);
}
if(op==)
{
int x;
ll z;
scanf("%d%lld",&x,&z);
z%=mod;
add(,in[x],out[x],z);
}
if(op==)
{
int x;
scanf("%d",&x);
ll ans=query(,in[x],out[x]);
printf("%lld\n",ans);
}
}
return ;
}