树剖 LCA DFS序板子题
#include<bits/stdc++.h> #define rep(i,a,n) for(int i=a;i<=n;++i) #define per(i,a,n) for(int i=n;i>=a;--i) #define pb push_back #define fi first #define se second #define io std::ios::sync_with_stdio(false) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int P = 1e9+7, INF = 0x3f3f3f3f; inline int lson(int x){return x*2;} inline int rson(int x){return x*2+1;} const int maxn=1e5+50; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } ll qpow(ll a,ll n) { ll r=1%P; for (a%=P; n; a=a*a%P,n>>=1)if(n&1)r=r*a%P; return r; } ll pos[maxn],out[maxn],top[maxn],cnt; ll a[maxn],b[maxn]; ll sum[maxn*4],tag[maxn*4]; ll _next[maxn*2],head[maxn],tot,to[maxn*2]; ll sz[maxn]; ll f[maxn]; ll n,m; void add(ll x,ll y) { _next[++tot]=head[x],head[x]=tot,to[tot]=y; _next[++tot]=head[y],head[y]=tot,to[tot]=x; } void dfs(ll u,ll fa) { sz[u]=1; f[u]=fa; for(ll i=head[u];i;i=_next[i]) { ll v=to[i]; if(v==fa)continue; dfs(v,u); sz[u]+=sz[v]; } } void dfs2(ll u,ll fa,ll t) { ll _max=-1; ll son=-1; pos[u]=out[u]=++cnt; b[cnt]=a[u]; top[u]=t; for(ll i=head[u];i;i=_next[i]) { ll v=to[i]; if(v==fa) continue; if(sz[v]>_max) _max=sz[v],son=v; } if(son!=-1) dfs2(son,u,t); for(ll i=head[u];i;i=_next[i]) { ll v=to[i]; if(v==fa||v==son) continue; dfs2(v,u,v); } out[u]=cnt; } void build(ll id, ll l,ll r) { if(l==r) { sum[id]=b[l]; return ; } ll mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); sum[id]=sum[id*2]+sum[id*2+1]; } void pushdown(ll l,ll r,ll id) { if(l==r)return ; ll t=tag[id]; tag[id]=0; tag[id*2]+=t; tag[id*2+1]+=t; ll mid=(l+r)/2; sum[id*2]+=(mid-l+1)*t; sum[id*2+1]+=(r-mid)*t; } void update(ll id,ll l,ll r,ll ql,ll qr,ll k) { if(tag[id]!=0)pushdown(l,r,id); if(l>=ql&&r<=qr) { tag[id]+=k; sum[id]+=(r-l+1)*k; return ; } ll mid=(l+r)/2; if(mid>=ql)update(id*2,l,mid,ql,qr,k); if(mid<qr)update(id*2+1,mid+1,r,ql,qr,k); sum[id]=sum[id*2]+sum[id*2+1]; } ll query(ll id,ll l,ll r,ll ql,ll qr) { if(tag[id]!=0)pushdown(l,r,id); if(l>=ql&&r<=qr)return sum[id]; ll ans=0; ll mid=(l+r)/2; if(mid>=ql)ans+=query(id*2,l,mid,ql,qr); if(mid<qr)ans+=query(id*2+1,mid+1,r,ql,qr); return ans; } ll answer(ll x) { ll ans=0; while(x!=0) { ans+=query(1,1,n,pos[top[x]],pos[x]); x=top[x]; x=f[x]; } return ans; } int main() { scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++) scanf("%lld",a+i); for(ll i=1;i<n;i++) { ll y,x; scanf("%lld%lld",&x,&y); add(x,y); } dfs(1,0); dfs2(1,0,1); build(1,1,n); while(m--) { ll op,x,p; scanf("%lld",&op); if(op==1) { scanf("%lld%lld",&x,&p); update(1,1,n,pos[x],pos[x],p); } if(op==2) { scanf("%lld%lld",&x,&p); update(1,1,n,pos[x],out[x],p); } if(op==3) { scanf("%lld",&x); printf("%lld ",answer(x)); } } }