讲真 sublime挺好用的。
//Stay foolish,stay hungry,stay young,stay simple #include<iostream> #include<cstdio> #include<cctype> #define ls now<<1 #define rs now<<1|1 #define int long long using namespace std; const int MAXN=100005; inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f; } struct Edge{ int next,to; }e[MAXN<<1]; int ecnt,head[MAXN]; inline void add(int x,int y){ e[++ecnt].next = head[x]; e[ecnt].to = y; head[x] = ecnt; } int n,m,r,p; int a[MAXN]; int w[MAXN]; struct Node{ int val,lazy; }node[MAXN<<2]; void pushup(int now){ node[now].val = node[ls].val + node[rs].val ; return; } void pushdown(int now,int l,int r){ node[ls].lazy +=node[now].lazy ; node[rs].lazy +=node[now].lazy ; int mid=(l+r)>>1; node[ls].val +=node[now].lazy *(mid-l+1); node[rs].val +=node[now].lazy *(r-mid); node[now].lazy = 0; } void build(int l,int r,int now){ if(l==r){ node[now].val = a[l]%p; return; } int mid=(l+r)>>1; build(l,mid,ls); build(mid+1,r,rs); pushup(now); } void updata(int L,int R,int l,int r,int now,int w){ if(L<=l&&r<=R){ node[now].lazy += w; node[now].val += w*(r-l+1); return; } pushdown(now,l,r); int mid=(l+r)>>1; if(L<=mid) updata(L,R,l,mid,ls,w); if(mid <R) updata(L,R,mid+1,r,rs,w); pushup(now); } int query(int L,int R,int l,int r,int now){ if(L<=l&&r<=R){ return node[now].val ; } pushdown(now,l,r); int mid=(l+r)>>1; int ret=0; if(L<=mid) ret+=query(L,R,l,mid,ls); if(mid <R) ret+=query(L,R,mid+1,r,rs); return ret; } int siz[MAXN],fa[MAXN],son[MAXN],dep[MAXN]; void dfs1(int x,int pre,int dp){ siz[x]=1;fa[x]=pre,dep[x]=dp+1; int mx=-1; for(int i=head[x];i;i=e[i].next){ int v=e[i].to; if(v==pre) continue; dfs1(v,x,dp+1); siz[x]+=siz[v]; if(mx<siz[v]){ son[x]=v; mx=siz[v]; } } } int id[MAXN],top[MAXN],tim=0; void dfs2(int x,int tp){ top[x]=tp;id[x]=++tim; a[tim]=w[x]; if(son[x]) dfs2(son[x],tp); for(int i=head[x];i;i=e[i].next){ int v=e[i].to; if(v==fa[x]||v==son[x]) continue; dfs2(v,v); } } int query_link(int x,int y){ int ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); ans+=query(id[top[x]],id[x],1,n,1); ans%=p; x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); ans+=query(id[x],id[y],1,n,1); ans%=p; return ans; } void updata_link(int x,int y,int k){ k%=p; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); updata(id[top[x]],id[x],1,n,1,k); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); updata(id[x],id[y],1,n,1,k); } int query_son(int x){ return query(id[x],id[x]+siz[x]-1,1,n,1)%p; } void updata_son(int x,int w){ w%=p; updata(id[x],id[x]+siz[x]-1,1,n,1,w); } signed main(){ // freopen("test.txt","w",stdout); n=rd(); m=rd(); r=rd(); p=rd(); for(int i=1;i<=n;i++) w[i]=rd(); for(int i=1;i< n;i++){ int x,y; x=rd();y=rd(); add(x,y); add(y,x); } dfs1(r,0,0); dfs2(r,r); build(1,n,1); // for(int i=1;i<=n;i++) cout<<id[i]<<" "; for(int i=1;i<=m;i++){ int q=rd(); int x,y,z; switch(q){ case 1:{ x=rd();y=rd();z=rd(); updata_link(x,y,z); break; } case 2:{ x=rd();y=rd(); cout<<query_link(x,y)%p<<endl; break; } case 3:{ x=rd();y=rd(); updata_son(x,y); break; } case 4:{ x=rd(); cout<<query_son(x)%p<<endl; break; } } } return 0; } ;