题目描述
Harry Potter 新学了一种魔法：可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。
这棵果树共有N个节点，其中节点0是根节点，每个节点u的父亲记为fa[u]，保证有fa[u] < u。初始时，这棵果树上的果子都被 Dumbledore 用魔法清除掉了，所以这个果树的每个节点上都没有果子（即0个果子）。
不幸的是，Harry 的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry 的魔法可以这样描述：
Add u v d
表示将点u和v之间的路径上的所有节点的果子个数都加上d。
接下来，为了方便检验 Harry 的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：
Query u
表示当前果树中，以点u为根的子树中，总共有多少个果子？
输入
第一行一个正整数N (1 ≤ N ≤ 100000)，表示果树的节点总数，节点以0,1,…,N − 1标号，0一定代表根节点。
接下来N − 1行，每行两个整数a,b (0 ≤ a < b < N)，表示a是b的父亲。
接下来是一个正整数Q(1 ≤ ? ≤ 100000)，表示共有Q次操作。
后面跟着Q行，每行是以下两种中的一种：
-
A u v d，表示将u到v的路径上的所有节点的果子数加上d；0 ≤ u,v <N,0 < d < 100000
-
Q u，表示询问以u为根的子树中的总果子数，注意是包括u本身的。
输出
对于所有的Query操作，依次输出询问的答案，每行一个。答案可能会超过2^32 ，但不会超过10^15 。
样例输入
4 0 1 1 2 2 3 4 A 1 3 1 Q 0 Q 1 Q 2
样例输出
3 3 2
题解
树剖模版。
#include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define ll long long const int maxn=1e5+5; const int maxm=2e5+5; ll fir[maxn],to[maxm],nex[maxm],ecnt; ll n,m,r,p,w[maxn],cnt,op,x,y,z; ll wt[maxn],son[maxn],top[maxn],fa[maxn],sz[maxn],dep[maxn],id[maxn]; struct SegmentTree{ ll l,r,v,add; }st[maxn*4]; void add_edge(int u,int v){ nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v; } void dfs1(int x,int f,int deep){ dep[x]=deep; fa[x]=f; sz[x]=1; int maxson=-1; for(int e=fir[x];e;e=nex[e]){ int v=to[e]; if(v==f) continue; dfs1(v,x,deep+1); sz[x]+=sz[v]; if(sz[v]>maxson) maxson=sz[v],son[x]=v; } } void dfs2(int x,int topf){ top[x]=topf; id[x]=++cnt; wt[cnt]=w[x]; if(!son[x]) return ; dfs2(son[x],topf); for(int e=fir[x];e;e=nex[e]){ int v=to[e]; if(v==fa[x]||v==son[x]) continue; dfs2(v,v); } } void pushup(int root){ st[root].v=(st[root*2].v+st[root*2+1].v); } void build(int root,int l,int r){ st[root].l=l;st[root].r=r; if(l==r) st[root].v=wt[l]; else{ int m=l+r>>1; build(root*2,l,m); build(root*2+1,m+1,r); pushup(root); } } void pushdown(int root){ st[root*2].v=(st[root*2].v+st[root].add*(st[root*2].r-st[root*2].l+1)); st[root*2+1].v=(st[root*2+1].v+st[root].add*(st[root*2+1].r-st[root*2+1].l+1)); st[root*2].add=(st[root*2].add+st[root].add); st[root*2+1].add=(st[root*2+1].add+st[root].add); st[root].add=0; } void add(int root,int l,int r,int val){ if(st[root].l>r||st[root].r<l) return ; if(st[root].l>=l&&st[root].r<=r){ st[root].v=(st[root].v+val*(st[root].r-st[root].l+1)); st[root].add=(st[root].add+val); } else{ pushdown(root); add(root*2,l,r,val); add(root*2+1,l,r,val); pushup(root); } } ll query(int root,int l,int r){ if(st[root].l>r||st[root].r<l) return 0; if(st[root].l>=l&&st[root].r<=r) return st[root].v; pushdown(root); return (query(root*2,l,r)+query(root*2+1,l,r)); } void Change(int x,int y,int val){ int f1=top[x],f2=top[y]; while(f1!=f2){ if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y); add(1,id[f1],id[x],val); x=fa[f1];f1=top[x]; } if(dep[x]>dep[y]) swap(x,y); add(1,id[x],id[y],val); } ll Query(int x,int y){ ll f1=top[x],f2=top[y],ans=0; while(f1!=f2){ if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y); ans=(ans+query(1,id[f1],id[x])); x=fa[f1];f1=top[x]; } if(dep[x]>dep[y]) swap(x,y); ans=(ans+query(1,id[x],id[y])); return ans; } void Change_tree(int x,int val){ add(1,id[x],id[x]+sz[x]-1,val); } ll Query_tree(int x){ return query(1,id[x],id[x]+sz[x]-1); } template<typename T>void read(T& aa){ char cc; ll ff;aa=0;cc=getchar();ff=1; while((cc<'0'||cc>'9')&&cc!='-') cc=getchar(); if(cc=='-') ff=-1,cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); aa*=ff; } int main(){ read(n); for(int i=1;i<n;i++){ read(x),read(y); add_edge(x+1,y+1); add_edge(y+1,x+1); } dfs1(1,0,1); dfs2(1,1); build(1,1,cnt); read(m); while(m--){ char o; cin>>o; if(o=='A'){ read(x),read(y),read(z); Change(x+1,y+1,z); } else{ read(x); cout<<Query_tree(x+1)<<endl; } } return 0; }