萌新刚学树剖,调了半天了,样例过了20分,快吐了,恳请大佬帮忙调一下
#include<bits/stdc++.h>
# define reg register
# define N (500005)
using namespace std;
struct node{
int l;
int r;
int sum;
int lazy;
}t[N];
int n,m,r,P;
int num[N];
int head[N],nxt[N],to[N],tot;
int rev[N],seg[N],top[N],fa[N],size[N],son[N],dep[N],sum;
inline int read(){
char c=getchar();reg int sum=0,f=1;
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c<='9'&&c>='0'){sum=sum*10+c-'0';c=getchar();}
return sum*f;
}
inline void update(const int &p){
if(t[p].lazy){
t[p<<1].lazy=(t[p<<1].lazy+t[p].lazy)%P;
t[p<<1|1].lazy=(t[p<<1|1].lazy+t[p].lazy)%P;
t[p<<1].sum+=(t[p<<1].r-t[p<<1].l+1)*t[p].lazy%P;
t[p<<1|1].sum+=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].lazy%P;
t[p].lazy=0;
}
}
void build(const int &p,const int &l,const int &r){
t[p].l=l;
t[p].r=r;
t[p].sum=0;
t[p].lazy=0;
if(l==r){
t[p].sum=num[rev[l]];
return;
}
reg int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%P;
}
void change(const int &p,const int &l,const int &r,const int &k){
if(t[p].l>=l&&t[p].r<=r){
t[p].lazy=(t[p].lazy+k)%P;
t[p].sum=(t[p].sum+(t[p].r-t[p].l+1)*k%P)%P;
return;
}
update(p);
reg int mid=t[p].l+t[p].r>>1;
if(mid>=l)change(p<<1,l,r,k);
if(mid<r)change(p<<1|1,l,r,k);
t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%P;
}
int query(const int &p,const int &l,const int &r){
if(t[p].l>=l&&t[p].r<=r)return t[p].sum;
update(p);
reg int mid=t[p].l+t[p].r>>1,ans=0;
if(mid>=l)ans+=query(p<<1,l,r);
if(mid<r)ans+=query(p<<1|1,l,r);
return ans;
}
inline void add(const int &x,const int &y){
to[++tot]=y;nxt[tot]=head[x];head[x]=tot;
to[++tot]=x;nxt[tot]=head[y];head[y]=tot;
}
void dfs1(const int &u,const int &f){
reg int v;
size[u]=1;
fa[u]=f;
dep[u]=dep[f]+1;
for(reg int i=head[u];i;i=nxt[i]){
v=to[i];
if(v==f)continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])
son[u]=v;
}
}
void dfs2(const int &u,const int &r){
reg int v;
seg[u]=++sum;
rev[sum]=u;
top[u]=r;
if(!son[u])return;
dfs2(son[u],r);
for(reg int i=head[u];i;i=nxt[i]){
v=to[i];
if(!top[v])
dfs2(v,v);
}
}
inline void ask1(int x,int y,int z){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[x]<dep[y])swap(x,y),swap(fx,fy);
change(1,seg[fx],seg[x],z);
x=fa[fx];fx=top[x];
}
if(dep[x]>dep[y])change(1,seg[y],seg[x],z);
else change(1,seg[x],seg[y],z);
}
inline int ask2(int x,int y){
int ans=0;
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[x]<dep[y])swap(x,y),swap(fx,fy);
ans=(ans+query(1,seg[fx],seg[x]))%P;
x=fa[fx];fx=top[x];
}
if(dep[x]>dep[y])ans=(ans+query(1,seg[y],seg[x]))%P;
else ans=(ans+query(1,seg[x],seg[y]))%P;
return ans;
}
inline void ask3(const int &x,const int &z){change(1,seg[x],seg[x]+size[x]-1,z);}
inline int ask4(const int &x){return query(1,seg[x],seg[x]+size[x]-1);}
int main(){
reg int i,j,k,x,y,z;
n=read();m=read();r=read();P=read();
for(i=1;i<=n;++i)
num[i]=read();
for(i=1;i<n;++i){
x=read();
y=read();
add(x,y);
}
dfs1(r,0);
dfs2(r,r);
build(1,1,n);
for(i=1;i<=m;++i){
k=read();
if(k==1){
x=read();y=read();z=read();
ask1(x,y,z);
}
if(k==2){
x=read();y=read();
printf("%d\n",ask2(x,y));
}
if(k==3){
x=read();z=read();
ask3(x,z);
}
if(k==4){
x=read();
printf("%d\n",ask4(x));
}
}
return 0;
}