代码如下
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
struct node{
int nxt,to;
ll dis;
}e[N];
//id表示dfs序，top表示链顶，siz表示子树大小，son表示重儿子编号，f表示父亲编号
//num表示边数，ww表示原节点值，w表示线段树上的值，s为线段树
int num,head[N],top[N],f[N],dep[N],siz[N],id[N],cnt,son[N];
ll s[N<<2],tag[N<<2],mod,ww[N],w[N];
void add(int x,int y){
e[++num].to=y;
e[num].nxt=head[x];
head[x]=num;
}
int n,m,r;//树链剖分部分
void dfs1(int u,int fa){
f[u]=fa;
dep[u]=dep[fa]+1;
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs1(v,u);
siz[u]+=siz[v];
if(!son[u]||siz[v]>siz[son[u]])
son[u]=v;
}
}
void dfs2(int u,int val){
top[u]=val;
id[u]=++cnt;
w[cnt]=ww[u];
if(!son[u])return;
dfs2(son[u],val);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v!=son[u]&&v!=f[u])dfs2(v,v);
}
}
void pushup(int k){//合并
s[k]=(s[k*2]+s[k*2+1])%mod;
}
void addtag(int k,int l,int r,ll val){//懒标记下传
s[k]=(s[k]+ll(r-l+1)*val)%mod;
tag[k]+=val;tag[k]%mod;
}
void pushdown(int k,int l,int r){
int mid=(l+r)>>1;
addtag(k*2,l,mid,tag[k]);
addtag(k*2+1,mid+1,r,tag[k]);
tag[k]=0;
}
void build(int k,int l,int r){//建树
if(l==r){
s[k]=w[l];
return;
}
int mid=(l+r)>>1;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
pushup(k);
}
ll query(int k,int l,int r,int x,int y){//线段树询问
if(l>y||r<x)return 0;
if(l>=x&&r<=y)return s[k]%mod;
int mid=(l+r)>>1;
pushdown(k,l,r);
return (query(k*2,l,mid,x,y)+query(k*2+1,mid+1,r,x,y))%mod;
}
void change(int k,int l,int r,int x,int y,ll val){//线段树改变
if(l>y||r<x)return;
if(l>=x&&r<=y){
addtag(k,l,r,val);
return;
}
int mid=(l+r)>>1;
pushdown(k,l,r);
change(k*2,l,mid,x,y,val);
change(k*2+1,mid+1,r,x,y,val);
pushup(k);
}
void update_range(int x,int y,ll val){//路径add
ll ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
change(1,1,n,id[top[x]],id[x],val);
x=f[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
change(1,1,n,id[x],id[y],val);
}
ll query_range(int x,int y){//路径求和
ll ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=(ans+query(1,1,n,id[x],id[top[x]]))%mod;
x=f[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans=(ans+query(1,1,n,id[x],id[y]))%mod;
}
void update_tree(int x,ll val){change(1,1,n,id[x],id[x]+siz[x]-1,val);}//子树改变
ll query_tree(int x){return query(1,1,n,id[x],id[x]+siz[x]-1);}//子树求和
int main(){
//freopen("P3384_1.in","r",stdin);
scanf("%d%d%d%lld",&n,&m,&r,&mod);
for(int i=1;i<=n;i++)scanf("%lld",&ww[i]);
for(int i=1,x,y;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs1(r,0);
dfs2(r,r);
build(1,1,n);
while(m--){
int op,x;ll y,z;
scanf("%d",&op);
switch(op){
case 1:scanf("%d%d%lld",&x,&y,&z);update_range(x,y,z);break;
case 2:scanf("%d%d",&x,&y);printf("%lld\n",query_range(x,y));break;
case 3:scanf("%d%lld",&x,&y);update_tree(x,y);break;
case 4:scanf("%d",&x);printf("%lld\n",query_tree(x));break;
}
}
return 0;
}
```
by liaoz123 @ 2023-01-11 09:36:00
已AC，谢谢大家
by liaoz123 @ 2023-01-11 10:08:48