传送门
模板题，dfs的时候不小心傻逼地写错了。。记一下。。
#include<bits/stdc++.h> #define len(x) (T[x].r-T[x].l+1) #define lc (root<<1) #define rc (root<<1|1) #define mid ((T[root].l+T[root].r)>>1) using namespace std; const int maxn=1e5+10; struct node{int l,r,sum,add;}T[maxn<<2]; int Head[maxn],Next[maxn<<1],V[maxn<<1]; int son[maxn],fa[maxn],siz[maxn],dep[maxn],top[maxn],dfn[maxn],t[maxn]; int N,M,R,mod,u,v,op,w,cnt=0,tot=0,a[maxn]; inline int read(){ int x=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x; } void print(int x){ if(x>9) print(x/10); putchar(x%10+48); } inline int plu(const int &a,const int &b){return (a+b>=mod)?((a+b)%mod):(a+b);} inline int mul(const int &a,const int &b){return a*b%mod;} inline void pushup(int root){T[root].sum=plu(T[lc].sum,T[rc].sum);} inline void pushdown(int root){ if(T[root].add){ T[lc].sum=plu(T[lc].sum,mul(T[root].add,len(lc))); T[rc].sum=plu(T[rc].sum,mul(T[root].add,len(rc))); T[lc].add=plu(T[lc].add,T[root].add); T[rc].add=plu(T[rc].add,T[root].add); T[root].add=0; } } void build(int root,int l,int r){ T[root].l=l,T[root].r=r; if(l==r){ T[root].sum=a[t[l]]; return; } build(lc,l,mid),build(rc,mid+1,r); pushup(root); } void update(int root,int L,int R,int C){ if(L<=T[root].l&&R>=T[root].r){ T[root].sum=plu(T[root].sum,mul(C,len(root))); T[root].add=plu(T[root].add,C); return; } pushdown(root); if(L<=mid) update(lc,L,R,C); if(R>mid ) update(rc,L,R,C); pushup(root); } int query(int root,int L,int R){ if(L<=T[root].l&&R>=T[root].r) return T[root].sum; pushdown(root); int ret=0; if(L<=mid) ret=plu(ret,query(lc,L,R)); if(R>mid ) ret=plu(ret,query(rc,L,R)); return ret; } void dfs1(int u,int f){ fa[u]=f,siz[u]=1,son[u]=0; for(int i=Head[u];i;i=Next[i]){ int v=V[i];if(v==f) continue; dep[v]=dep[u]+1,dfs1(v,u),siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } void dfs2(int u,int tp){ top[u]=tp,t[dfn[u]=++tot]=u; if(!son[u]) return; dfs2(son[u],tp); for(int i=Head[u];i;i=Next[i]){ int v=V[i];if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } inline void add(int u,int v){ ++cnt; Next[cnt]=Head[u]; V[cnt]=v; Head[u]=cnt; } inline void addedge(int u,int v){add(u,v),add(v,u);} inline void change(int u,int v,int w){ int fu=top[u],fv=top[v]; while(fu!=fv){ if(dep[fu]<dep[fv]) swap(u,v),swap(fu,fv); update(1,dfn[fu],dfn[u],w),u=fa[fu],fu=top[u]; } if(dep[v]<dep[u]) swap(u,v); update(1,dfn[u],dfn[v],w); } inline int ask(int u,int v){ int ret=0,fu=top[u],fv=top[v]; while(fu!=fv){ if(dep[fu]<dep[fv]) swap(u,v),swap(fu,fv); ret=plu(ret,query(1,dfn[top[u]],dfn[u])),u=fa[fu],fu=top[u]; } if(dep[u]>dep[v]) swap(u,v); return plu(ret,query(1,dfn[u],dfn[v])); } int main(){ N=read(),M=read(),R=read(),mod=read(); for(int i=1;i<=N;++i) a[i]=read(); for(int i=1;i<N ;++i) u=read(),v=read(),addedge(u,v); dfs1(R,0),dfs2(R,R),build(1,1,N); while(M--){ op=read(); if(op==1) u=read(),v=read(),w=read(),change(u,v,w); if(op==2) u=read(),v=read(),print(ask(u,v)),putchar('\n'); if(op==3) u=read(),w=read(),update(1,dfn[u],dfn[u]+siz[u]-1,w); if(op==4) u=read(),print(query(1,dfn[u],dfn[u]+siz[u]-1)),putchar('\n'); } }
