@[little_coco](/user/149219)
by JK_LOVER @ 2020-08-23 11:22:43
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,r,mod,a[100005],tree[400005],tree1[400005],lazytag[400005];
int zhong[100005],size[100005],ceng[100005];
int tot=0,st[500001],to[500001<<1],nx[500001<<1],fa[500001];
int son[5000001];
int dfsxu,id[500001],top[500001],rk[500001];
void add(int u,int v){
to[++tot]=v;
nx[tot]=st[u];
st[u]=tot;
}
int ls(int p){
return p*2;
}
int rs(int p){
return p*2+1;
}
void push_up(int p){
tree[p]=tree[ls(p)]+tree[rs(p)];
tree[p]%=mod;
}
void dfs(int now,int father){
int maxx=0;
size[now]=1;
for(int i=st[now];i;i=nx[i]){
int v=to[i];
// cout<<"%%% "<<now<<' '<<v<<endl;
// cout<<"fa="<<fa[now]<<endl;
if(father!=v){
fa[v]=now;
// cout<<"%%% "<<v<<' '<<fa[v]<<' '<<now<<endl;
ceng[v]=ceng[now]+1;
dfs(v,now);
size[now]+=size[v];
if(maxx<size[v]){
maxx=size[v];
son[now]=v;
}
}
}
return;
}
void dfs2(int now,int fokeyou){
// cout<<"#$# "<<now<<" "<<fa[now]<<" "<<son[now]<<endl;
dfsxu++;
id[now]=dfsxu;
rk[dfsxu]=a[now];
top[now]=fokeyou;
if(son[now])dfs2(son[now],fokeyou);
for(int i=st[now];i;i=nx[i]){
int v=to[i];
// cout<<"$#$ "<<v<<" "<<fa[now]<<endl;
if(fa[now]!=v&&v!=son[now]){
dfs2(v,v);
}
}
return;
}
void build(int l,int r,int p){
if(l==r){
tree[p]=rk[l];
tree[p]%=mod;
return;
}
int mid=(l+r)/2;
build(l,mid,ls(p));
build(mid+1,r,rs(p));
push_up(p);
}
void c(long long l,long long r,long long p,long long k){
tree[k]+=p*(r-l+1);
lazytag[k]+=p;
lazytag[k]%=mod;
tree[k]%=mod;
}
void push_down(long long l,long long r,long long p,long long k){
long long mid=(l+r)/2;
c(l,mid,p,ls(k));
c(mid+1,r,p,rs(k));
lazytag[k]=0;
}
void change(int l,int r,int fl,int fr,int p,int k){
if(l>=fl&&r<=fr){
// cout<<l<<' '<<r<<' '<<fl<<' '<<fr<<' '<<p<<' '<<k<<endl;
tree[k]+=p*(r-l+1);
tree[k]%=mod;
lazytag[k]+=p;
lazytag[k]%=mod;
return ;
}
push_down(l,r,lazytag[k],k);
long long mid=(l+r)/2;
if(fl<=mid)change(l,mid,fl,fr,p,ls(k));
if(fr>mid)change(mid+1,r,fl,fr,p,rs(k));
push_up(k);
}
int findhe(int l,int r,int fl,int fr,int k){
if(l>=fl&&r<=fr){
return tree[k];
}
push_down(l,r,lazytag[k],k);
long long mid=(l+r)/2,ans=0;
if(fl<=mid)ans+=findhe(l,mid,fl,fr,ls(k));
ans%=mod;
if(fr>mid)ans+=findhe(mid+1,r,fl,fr,rs(k));
ans%=mod;
return ans;
}
inline int qRange(int x,int y){
int ans=0;
// cout<<"xiaoke"<<ans;
while(top[x]!=top[y]){
if(ceng[top[x]]<ceng[top[y]])swap(x,y);//aaaaaaaaaaaaaaaaaaaaa
ans+=findhe(1,n,id[top[x]],id[x],1);
ans%=mod;
x=fa[top[x]];
}
if(ceng[x]>ceng[y])swap(x,y);
ans+=findhe(1,n,id[x],id[y],1);
return ans%mod;
}
inline void updRange(int x,int y,int k){
k%=mod;
while(top[x]!=top[y]){
if(ceng[top[x]]<ceng[top[y]])swap(x,y);
change(1,n,id[top[x]],id[x],k,1);
x=fa[top[x]];
}
if(ceng[x]>ceng[y])swap(x,y);
change(1,n,id[x],id[y],k,1);
}
inline int qSon(int x){
// cout<<"dedededededededede"<<id[x]<<' '<<size[x]<<endl;
return findhe(1,n,id[x],id[x]+size[x]-1,1)%mod;;
}
inline void updSon(int x,int k){
// cout<<"dedededededededede"<<id[x]<<' '<<size[x]<<' '<<id[x]+size[x]-1<<endl;
change(1,n,id[x],id[x]+size[x]-1,k,1);
// cout<<findhe(1,n,1,n,1)<<endl;
}
signed main(){
scanf("%lld%lld%lld%lld",&n,&m,&r,&mod);
int u,v;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<n;i++){
scanf("%lld%lld",&u,&v);
// cout<<"*** "<<u<<' '<<v<<endl;
add(u,v);
add(v,u);
}
int k;
ceng[r]=1;
fa[r]=r;
// cout<<r<<endl;
dfs(r,0);
// cout<<"^^^ "<<fa[2]<<endl;
dfs2(r,r);
build(1,n,1);
for(int i=1;i<=m;i++){
// int k;
scanf("%lld",&k);
if(k==1){
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
updRange(x,y,z);
}
if(k==2){
int x,y;
scanf("%lld%lld",&x,&y);
cout<<qRange(x,y)%mod<<endl;
}
if(k==3){
int x,y;
scanf("%lld%lld",&x,&y);
updSon(x,y);
}
if(k==4){
int x;
scanf("%lld",&x);
cout<<qSon(x)%mod<<endl;
}
}
return 0;
}
```
by JK_LOVER @ 2020-08-23 11:22:59
~~~
while(top[x]!=top[y]){
if(ceng[top[x]]<ceng[top[y]])swap(x,y);//aaaaaaaaaaaaaaaaaaaaa
ans+=findhe(1,n,id[top[x]],id[x],1);
ans%=mod;
x=fa[top[x]];
}
~~~
马蜂差评 ||@[little_coco](/user/149219)
by JK_LOVER @ 2020-08-23 11:23:44
@[JK_LOVER](/user/227824) 懂了，谢谢qwq
by _maze @ 2020-08-23 11:58:24