刚学树剖,一边看题解一边看一本通,写出了一个不知道哪错的玩意。求大佬们抽出一点宝贵的时间帮我看看。。。
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ls k<<1
#define rs k<<1|1
#define Rint register int
using namespace std;
inline int gin(){
char c=getchar();
int s=0,f=1;
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*f;
}
const int N=2e5+5;
int n,m,r,ans=0,tot=0,mod,a[N],sum[N<<2],tag[N<<2],head[N],fa[N],son[N],seg[N],rev[N],dep[N],sz[N],top[N];
struct edge{
int ne,to;
}e[N];
inline void add(int x,int y){
e[++tot].to=y;
e[tot].ne=head[x];
head[x]=tot;
}
inline void dfs1(int u,int f){
sz[u]=1;
fa[u]=f;
dep[u]=dep[f]+1;
for(int i=head[u];i;i=e[i].ne){
int v=e[i].to;
if(v==f)continue;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]])son[u]=v;
}
}
inline void dfs2(int u,int f){
if(son[u]){
seg[son[u]]=++seg[0];
top[son[u]]=top[u];
rev[seg[0]]=son[u];
dfs2(son[u],u);
}
for(int i=head[u];i;i=e[i].ne){
int v=e[i].to;
if(top[v])continue;
seg[v]=++seg[0];
rev[seg[0]]=v;
top[v]=v;
dfs2(v,u);
}
}
inline void pushup(int k){
sum[k]=(sum[ls]+sum[rs])%mod;
}
inline void pushdown(int k,int len){
tag[ls]+=tag[k];
tag[rs]+=tag[k];
sum[ls]+=tag[k]*(len-(len>>1));
sum[rs]+=tag[k]*(len>>1);
sum[ls]%=mod;
sum[rs]%=mod;
tag[k]=0;
}
inline void build(int k,int l,int r){
if(l==r){
sum[k]=a[rev[l]];
if(sum[k]>mod)sum[k]%=mod;
return;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(k);
}
inline void change(int k,int l,int r,int L,int R,int z){
if(L<=l&&r<=R){
tag[k]+=z;
sum[k]+=k*(r-l+1);
return;
}
int mid=l+r>>1;
if(tag[k])pushdown(k,r-l+1);
if(L<=mid)change(ls,l,mid,L,R,z);
if(R>mid) change(rs,mid+1,r,L,R,z);
pushup(k);
}
inline void query(int k,int l,int r,int L,int R){
if(L<=l&&r<=R){
ans+=sum[k];
ans%=mod;
return;
}
int mid=l+r>>1;
if(tag[k])pushdown(k,r-l+1);
if(L<=mid)query(ls,l,mid,L,R);
if(R>mid) query(rs,mid+1,r,L,R);
}
inline int ask1(int x,int y){
ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
query(1,1,seg[0],seg[top[x]],seg[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
query(1,1,seg[0],seg[x],seg[y]);
return ans%mod;
}
inline void upd1(int x,int y,int z){
z%=mod;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
change(1,1,seg[0],seg[top[x]],seg[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
change(1,1,seg[0],seg[x],seg[y],z);
}
inline int ask2(int x){
ans=0;
query(1,1,seg[0],seg[x],seg[x]+sz[x]-1);
return ans;
}
inline void upd2(int x,int z){
change(1,1,seg[0],seg[x],seg[x]+sz[x]-1,z);
}
int main(){
n=gin(),m=gin(),r=gin(),mod=gin();
for(Rint i=1;i<=n;i++)a[i]=gin();
for(Rint i=1;i< n;i++){
int x=gin(),y=gin();
add(x,y);add(y,x);
}
dep[0]=0;
dfs1(r,0);
dfs2(r,0);
build(1,1,n);
while(m--){
int k=gin(),x,y,z;
if(k==1){
x=gin(),y=gin(),z=gin();
upd1(x,y,z);
}
else if(k==2){
x=gin(),y=gin();
printf("%d\n",ask1(x,y));
}
else if(k==3){
x=gin(),z=gin();
upd2(x,z);
}
else {
x=gin();
printf("%d\n",ask2(x));
}
}
return 0;
}