讲真 sublime挺好用的。
atom更吼
#include<iostream> #include<cstdio> #define int long long using namespace std; const int MAXN=1000005; 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; } int n,m,root,p; int w[MAXN],data[MAXN]; struct Edge{ int next,to; }e[MAXN<<1]; int ecnt=1,head[MAXN]; inline void adde(int x,int y){ e[++ecnt].next = head[x]; e[ecnt].to = y; head[x] = ecnt; } #define mid ((l+r)>>1) #define ls (cur<<1) #define rs (cur<<1|1) int val[MAXN],add[MAXN]; inline void pushup(int cur){val[cur]=val[ls]+val[rs];} inline void pushdown(int cur,int l,int r){ (add[ls]+=add[cur])%=p; (add[rs]+=add[cur])%=p; (val[ls]+=add[cur]*(mid-l+1))%=p; (val[rs]+=add[cur]*(r-mid))%=p; add[cur]=0; } void build(int cur,int l,int r){ if(l==r) {val[cur]=data[l];return;} build(ls,l,mid); build(rs,mid+1,r); pushup(cur); } int query(int L,int R,int cur,int l,int r){ if(L<=l&&r<=R) return val[cur]%p; pushdown(cur,l,r); int ret=0; if(L<=mid) ret+=query(L,R,ls,l,mid); if(mid <R) ret+=query(L,R,rs,mid+1,r); return ret; } void update(int L,int R,int cur,int l,int r,int w){ if(L<=l&&r<=R){ (add[cur]+=w)%=p; (val[cur]+=w*(r-l+1))%=p; return; } pushdown(cur,l,r); if(L<=mid) update(L,R,ls,l,mid,w); if(mid <R) update(L,R,rs,mid+1,r,w); pushup(cur); } int fa[MAXN],dep[MAXN],hs[MAXN],siz[MAXN]; void dfs1(int cur,int pre){ fa[cur]=pre;dep[cur]=dep[pre]+1;siz[cur]=1; int mx=-1; for(int i=head[cur];i;i=e[i].next){ int v=e[i].to; if(v==pre) continue; dfs1(v,cur); siz[cur]+=siz[v]; if(siz[v]>mx){mx=siz[v];hs[cur]=v;} } } int top[MAXN],id[MAXN],tim; void dfs2(int cur,int tp){ id[cur]=++tim;top[cur]=tp;data[tim]=w[cur]; if(hs[cur]) dfs2(hs[cur],tp); for(int i=head[cur];i;i=e[i].next){ int v=e[i].to; if(v==fa[cur]||v==hs[cur]) continue; dfs2(v,v); } } int query_link(int x,int y){ int ret=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); ret+=query(id[top[x]],id[x],1,1,n); ret%=p;x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); ret+=query(id[x],id[y],1,1,n);ret%=p; return ret; } void update_link(int x,int y,int w){ w%=p; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); update(id[top[x]],id[x],1,1,n,w); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); update(id[x],id[y],1,1,n,w); } int query_subTree(int x){ return query(id[x],id[x]+siz[x]-1,1,1,n)%p; } void update_subTree(int x,int w){ update(id[x],id[x]+siz[x]-1,1,1,n,w%p); } main(){ n=rd(); m=rd(); root=rd(); p=rd(); for(int i=1;i<=n;i++)w[i]=rd(); int x,y,z,q; for(int i=1;i<=n-1;i++){ x=rd(); y=rd(); adde(x,y); adde(y,x); } dfs1(root,0); dfs2(root,root); build(1,1,n); for(int i=1;i<=m;i++){ q=rd(); switch(q){ case 1:{ x=rd(); y=rd(); z=rd(); update_link(x,y,z%p); break; } case 2:{ x=rd(); y=rd(); printf("%lld ",query_link(x,y)); break; } case 3:{ x=rd(); y=rd(); update_subTree(x,y); break; } case 4:{ x=rd(); printf("%lld ",query_subTree(x)); break; } } } return 0; }