蒟蒻初次尝试树剖,尝试过修改之前讨论里的炸 long long 问题,全改成了 long long 且乘法加法运算封装了。但还是 WA30
die码如下:
#include <bits/stdc++.h>
#define debug puts("I ak IOI several times");
#define pb push_back
#define int long long
using namespace std;
template <typename T>inline void read(T& t){
t=0; register char ch=getchar(); register int fflag=1;
while(!('0'<=ch&&ch<='9')){if(ch=='-') fflag=-1;ch=getchar();}
while(('0'<=ch&&ch<='9')){t=((t<<1)+(t<<3))+ch-'0'; ch=getchar();} t*=fflag;
}
template <typename T,typename... Args> inline void read(T& t, Args&... args){
read(t);read(args...);
}
template <typename T>inline void write(T x){
if(x<0) putchar('-'),x=~(x-1); int s[40],top=0;
while(x) s[++top]=x%10,x/=10; if(!top) s[++top]=0;
while(top) putchar(s[top--]+'0');
}
inline bool unat(int l,int r,int ll,int rr){return (r<ll)||(l>rr);}
inline bool ct(int l,int r,int ll,int rr){return (l<=ll)&&(r>=rr);}
inline bool in(int idx,int l,int r){return (idx>=l)&&(idx<=r);}
const int MAXN=1000086;
int P,newva[MAXN];
inline int Add(int x,int y){return (x+y)%P;}
inline int Mul(int x,int y){return x%P*y%P;}
struct Edge{
int to,nxt;
}e[MAXN];
struct Node{
int l,r;
long long v,tag;
};
struct Segment_Tree{
Node a[4000005];
#define ls(x) x<<1
#define rs(x) (x<<1)+1
void pushup(int x){
a[x].v=Add(a[ls(x)].v,a[rs(x)].v);
return;
}
void build_up(int l,int r,int idx){
a[idx].l=l;a[idx].r=r;
if(l==r){a[idx].v=newva[l]%P;return;}
int mid=Add(l,r)>>1;
build_up(l,mid,ls(idx));
build_up(mid+1,r,rs(idx));
pushup(idx);
return;
}
void tagg(int x,long long k){
a[x].v=Add(a[x].v,Mul(Add(a[x].r+1,-a[x].l),k));
a[x].tag=Add(a[x].tag,k);
return;
}
void pushdown(int x){
long long &tx=a[x].tag; tx%=P;
tagg(ls(x),tx);tagg(rs(x),tx);
tx=0;
return;
}
void Change(int l,int r,int rl,int rr,int idx,long long k){
if(a[idx].l>=rl&&a[idx].r<=rr){
//完全包含
a[idx].v=Add(a[idx].v,Mul((r-l+1),k));
a[idx].tag=Add(k,a[idx].tag);
return;
}
if(a[idx].l>rr||a[idx].r<rl) return;
pushdown(idx);
int mid=(l+r)>>1;
Change(l,mid,rl,rr,ls(idx),k);
Change(mid+1,r,rl,rr,rs(idx),k);
pushup(idx);
return;
}
long long query(int l,int r,int rl,int rr,int idx){
if(a[idx].l>=rl&&a[idx].r<=rr) return a[idx].v%P;
if(a[idx].l>rr||a[idx].r<rl) return 0;
pushdown(idx);
int mid=(l+r)>>1;
return Add(query(l,mid,rl,rr,ls(idx)),query(mid+1,r,rl,rr,rs(idx)));
}
}seg;
int head[MAXN],cnt,tot,n,id[MAXN],va[MAXN],m,Q,fa[MAXN],top[MAXN],dep[MAXN],sz[MAXN],zl[MAXN];
void add(int x,int y){
e[++cnt]={y,head[x]}; head[x]=cnt;
return;
}
void dfs1(int u,int f){
sz[u]=1; fa[u]=f;
dep[u]=dep[f]+1; zl[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f) continue;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[zl[u]]) zl[u]=v;
}
}
void dfs(int u,int tp){
top[u]=tp; id[u]=++tot;
newva[tot]=va[u]%P;
if(zl[u]) dfs(zl[u],tp);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==zl[u]||v==fa[u]) continue;
dfs(v,v);
}
}
void change(int u,int v,int val){
val%=P;
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]) swap(u,v);
//cout<<u<<' '<<v<<endl;
seg.Change(1,n,id[v],id[top[v]],1,val);
v=fa[top[v]];
}
if(dep[u]>dep[v]) swap(u,v);
seg.Change(1,n,id[u],id[v],1,val);
}
int Query_Range(int u,int v){
long long res=0;
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]) swap(u,v);
res=Add(res,seg.query(1,n,id[v],id[top[v]],1));
v=fa[top[v]];
}
if(dep[u]>dep[v]) swap(u,v);
res=Add(res,seg.query(1,n,id[u],id[v],1));
return res;
}
void ChAnGe(int x,int val){seg.Change(1,n,id[x],id[x]+sz[x]-1,1,val);}
int Get(int x){return seg.query(1,n,id[x],id[x]+sz[x]-1,1);}
signed main(){
read(n,m,Q,P);
for(int i=1;i<=n;++i) read(va[i]);
for(int i=1;i<n;++i){
int x,y;
read(x,y);
add(x,y);
add(y,x);
}
dfs1(Q,0);
dfs(Q,Q);
seg.build_up(1,n,1);
while(m--){
int opt;
read(opt);
if(opt==1){
int x,y,z;
read(x,y,z);
z%=P;
change(x,y,z);
}else{
if(opt==2){
int x,y;
read(x,y);
cout<<Query_Range(x,y)%P<<endl;
}else{
if(opt==3){
int x,va;
read(x,va);
ChAnGe(x,va);
}else{
int x;
read(x);
cout<<Get(x)%P<<endl;
}
}
}
}
return 0;
}