题目描述
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：
- 操作 1 ：把某个节点 x 的点权增加 a 。
- 操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
- 操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
输入格式
第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数，表示树中节点的初始权值。
接下来 N-1 行每行两个正整数 from, to ， 表示该树中存在一条边 (from, to) 。
再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。
输出格式
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
题解：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+100; typedef long long ll; int n,m; vector<int> g[maxn]; int son[maxn]; int id[maxn]; int fa[maxn]; int cnt; int dep[maxn]; int size[maxn]; int top[maxn]; int w[maxn]; int wt[maxn]; struct node { int l,r; ll sum; ll lazy; }segTree[maxn*4]; void build (int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; if (l==r) { segTree[i].sum=wt[l]; return; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum; } void spread (int i) { if (segTree[i].lazy) { segTree[i<<1].sum+=segTree[i].lazy*(segTree[i<<1].r-segTree[i<<1].l+1); segTree[i<<1|1].sum+=segTree[i].lazy*(segTree[i<<1|1].r-segTree[i<<1|1].l+1); segTree[i<<1].lazy+=segTree[i].lazy; segTree[i<<1|1].lazy+=segTree[i].lazy; segTree[i].lazy=0; } } void update (int i,int l,int r,int val) { if (l<=segTree[i].l&&segTree[i].r<=r) { segTree[i].sum+=(ll)val*(segTree[i].r-segTree[i].l+1); segTree[i].lazy+=val; return; } spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; if (l<=mid) update(i<<1,l,r,val); if (r>mid) update(i<<1|1,l,r,val); segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum; } ll query (int i,int l,int r) { if (l<=segTree[i].l&&segTree[i].r<=r) return segTree[i].sum; spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; ll ans=0; if (l<=mid) ans+=query(i<<1,l,r); if (r>mid) ans+=query(i<<1|1,l,r); return ans; } ll qRange (int x,int y) { ll ans=0; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans+=query(1,id[top[x]],id[x]); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); ans+=query(1,id[x],id[y]); return ans; } void upRange (int x,int y,int k) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); update(1,id[top[x]],id[x],k); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); update(1,id[x],id[y],k); } int qSon (int x) { return query(1,id[x],id[x]+size[x]-1); } int upSon (int x,int k) { update(1,id[x],id[x]+size[x]-1,k); } void dfs1 (int x,int f,int deep) { dep[x]=deep; fa[x]=f; size[x]=1; int maxson=-1; for (int y:g[x]) { if (y==f) continue; dfs1(y,x,deep+1); size[x]+=size[y]; if (size[y]>maxson) son[x]=y,maxson=size[y]; } } void dfs2 (int x,int topf) { id[x]=++cnt; wt[cnt]=w[x]; top[x]=topf; if (!son[x]) return; dfs2(son[x],topf); for (int y:g[x]) { if (y==fa[x]||y==son[x]) continue; dfs2(y,y); } } int main () { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",w+i); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } dfs1(1,0,1); dfs2(1,1); build(1,1,n); while (m--) { int op; scanf("%d",&op); if (op==1) { int x,y; scanf("%d%d",&x,&y); update(1,id[x],id[x],y); } else if (op==2) { int x,y; scanf("%d%d",&x,&y); upSon(x,y); } else if (op==3) { int x; scanf("%d",&x); printf("%lld ",qRange(1,x)); } } }