树剖求助,37pts

树剖求助,37pts```cpp #include<bits/stdc++.h> #define qwe(i,a,b) for(int i=a;i<=b;i++) #define itn int #define asn ans #define reisze resize #define ls ((u)<<1) #define rs ((u)<<1|1) #define LL long long using namespace std; constexpr int N=6e5+5; constexpr LL inf=1e12; vector G[N]; LL n,m,q,p; vector val; LL dfn[N],fa[N],son[N],top[N],dep[N],siz[N],rm[N]; LL tag[N],sum[N]; int cnt; void dfs1(int x,int f){ fa[x]=f; dep[x]=dep[f]+1; siz[x]=1; LL maxx=0; for(int ne:G[x]){ if(ne==f)continue; dfs1(ne,x); if(siz[ne]>maxx){ maxx=siz[ne]; son[x]=ne; } siz[x]+=siz[ne]; } } void dfs2(int x,int tp){ dfn[x]=++cnt; top[x]=tp; if(son[x])dfs2(son[x],tp); for(int ne:G[x]){ if(ne==son[x]||ne==fa[x])continue; dfs2(ne,ne); } rm[x]=cnt; } int LCA(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); x=fa[top[x]]; } return dep[x]>dep[y]?y:x; } void cov(int u,int l,int r,LL v){ tag[u]+=v; sum[u]+=((r-l+1)%p)*v%p; sum[u]%=p,tag[u]%=p; } void down(int u,int l,int r){ if(tag[u]){ int mid=(l+r)>>1; cov(ls,l,mid,tag[u]); cov(rs,mid+1,r,tag[u]); tag[u]=0; } } void up(int u){ sum[u]=(sum[ls]+sum[rs])%p; } void change(int u,int l,int r,int L,int R,LL v){ if(L<=l&&R>=r){ cov(u,l,r,v); return; } down(u,l,r); int mid=(l+r)>>1; if(L<=mid)change(ls,l,mid,L,R,v); if(R>mid)change(rs,mid+1,r,L,R,v); up(u); } LL query(int u,int l,int r,int L,int R){ if(L<=l&&R>=r)return sum[u]; down(u,l,r); int mid=(l+r)>>1; LL res=0; if(L<=mid)res+= query(ls,l,mid,L,R),res%=p; if(R>mid)res+= query(rs,mid+1,r,L,R),res%=p; return res; } void add1(itn x,int y,LL v){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); change(1,1,n,dfn[top[x]],dfn[x],v),x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); change(1,1,n,dfn[x],dfn[y],v); } LL ask1(int x,int y){ LL res=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); res+= query(1,1,n,dfn[top[x]],dfn[top[x]]),res%=p,x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); res+= query(1,1,n,dfn[x],dfn[y]); res%=p; return res; } void add2(int x,LL v){ change(1,1,n,dfn[x],rm[x],v); } LL ask2(int x){ return query(1,1,n,dfn[x],rm[x]); } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>n>>m>>q>>p; val.resize(n+1); for(int i=1;i<=n;i++)cin>>val[i]; for(int i=0;i<n-1;i++){ int u,v; cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } dfs1(q,0); dfs2(q,q); for(int i=1;i<=n;i++)add1(i,i,val[i]%p); for(int i=0;i<m;i++){ int op; cin>>op; int x,y; LL z; if(op==1){ cin>>x>>y>>z; z%=p; add1(x,y,z); }else if(op==2){ cin>>x>>y; cout<<ask1(x,y)%p<<'\n'; }else if(op==3){ cin>>x>>z; z%=p; add2(x,z); }else{ cin>>x; cout<<ask2(x)%p<<'\n'; } } }