树链剖分裸题:
树剖点这里：传送门
代码：
#include<bits/stdc++.h> #define sight(c) ('0'<=c&&c<='9') #define LL long long #define gc nc #define add(x,y) x+=(y) #define L(x) (x&-x) #define eho(x) for(int i=head[x];i;i=net[i]) #define N 100007 #define abs(x) ((x)>0?(x):(-x)) LL q1[N],q2[N],gg,sum[N],a[N],T,G; int tot,fall[N<<1],net[N<<1],head[N],top[N],son[N],f[N],dp[N],siz[N],be[N],ed[N],ok ,n,m,A,B,t[N],op,x,y,z,dla,OS; inline char nc(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++; } inline void swap(int &x,int &y) {x^=y; y^=x; x^=y;} inline void read(LL &x){ static char c; static int b; for(b=1,c=gc();!sight(c);c=gc()) if (c=='-') b=-1; for(x=0;sight(c);c=gc()) x=x*10+c-48; x*=b; } inline void read(int &x){ static char c; static int b; for(b=1,c=gc();!sight(c);c=gc()) if (c=='-') b=-1; for(x=0;sight(c);c=gc()) x=x*10+c-48; x*=b; } void write(LL x){if (x<10) {putchar('0'+x);return;}write(x/10); putchar('0'+x%10);} void writes(LL x){if (x<0) putchar('-'); write(abs(x));} inline void ADd(int x,int y) { fall[++tot]=y; net[tot]=head[x]; head[x]=tot; } inline void Add(LL *A,int x,LL dla) {for (;x<N;x+=L(x)) add(A[x],dla);} inline void adds(int l,int r,LL x) { Add(q1,l,x); Add(q1,r+1,-x); Add(q2,l,l*x); Add(q2,r+1,-(r+1)*x); } inline LL Query(LL *A,int x){for(G=0;x;x-=L(x)) add(G,A[x]);return G;} inline LL qurey(int l){ return (sum[l]+(l+1)*1ll*Query(q1,l)-Query(q2,l)); } void dfs(int x,int fa){ siz[x]=1; son[x]=-1; dp[x]=dp[fa]+1; f[x]=fa; eho(x) if (fall[i]^fa) { dfs(fall[i],x); siz[x]+=siz[fall[i]]; if ((!(~son[x]))||siz[fall[i]]>siz[son[x]]) son[x]=fall[i]; } } void dfs2(int x,int las){ t[++ok]=x;top[x]=las; be[x]=ok; if (~son[x]) dfs2(son[x],las); eho(x) if ((fall[i]^f[x])&&(fall[i]^son[x])) dfs2(fall[i],fall[i]); ed[x]=ok; } void apd(int x,int y,LL dla){ while (top[x]!=top[y]) { if (dp[top[x]]<dp[top[y]]) swap(x,y); adds(be[top[x]],be[x],dla); x=f[top[x]]; } if (dp[x]>dp[y]) swap(x,y); adds(be[x],be[y],dla); } LL query_path(int x,int y) { LL O=0; while (top[x]!=top[y]) { if (dp[top[x]]<dp[top[y]]) swap(x,y); add(O,qurey(be[x])-qurey(be[top[x]]-1)); x=f[top[x]]; } if (dp[x]>dp[y]) swap(x,y); add(O,qurey(be[y])-qurey(be[x]-1)); return O; } signed main () { // freopen("a.in","r",stdin); read(n); read(m); for (int i=1;i<=n;i++) read(a[i]); for (int i=1;i<n;i++) {read(A); read(B); ADd(A,B); ADd(B,A); } dfs(n,0); dfs2(n,n); for (int i=1;i<=n;i++) sum[i]=sum[i-1],add(sum[i],a[t[i]]); while (m--) { read(op); switch (op) { case 1: read(x); read(z); adds(be[x],be[x],z); break; case 2: read(x); read(z); adds(be[x],ed[x],z); break; case 3: read(x); writes(query_path(1,x)); putchar(' '); break; } } return 0; }