题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4372
本以为和 bzoj3730 一样，可以直接双倍经验了；
但要注意一下，树状数组不能查询0位置，所以再开一个 w 数组记录；
论 if 和 continue 的不同...如果要用到两个值，不要判断第一个后就 continue ...
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; typedef long long ll; int const xn=1e5+5; int n,hd[xn],ct,to[xn<<1],nxt[xn<<1],w[xn]; int siz[xn],fa[xn][20],dis[xn][20],dep[xn],mx,rt; bool vis[xn]; vector<ll>t[xn],fx[xn]; int rd() { int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return f?ret:-ret; } int Max(int x,int y){return x>y?x:y;} int Min(int x,int y){return x<y?x:y;} void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;} void getrt(int x,int ff,int sum) { siz[x]=1; int nmx=0; for(int i=hd[x],u;i;i=nxt[i]) { if((u=to[i])==ff||vis[u])continue; getrt(u,x,sum); siz[x]+=siz[u]; nmx=Max(nmx,siz[u]); } nmx=Max(nmx,sum-siz[x]); if(nmx<mx)mx=nmx,rt=x; } void build(int x,int ff,int d) { for(int i=hd[x],u;i;i=nxt[i]) { if((u=to[i])==ff||vis[u])continue; fa[u][++dep[u]]=rt; dis[u][dep[u]]=d; build(u,x,d+1); } } void work(int x,int sum) { vis[x]=1; build(x,0,1); t[x].resize(sum+1); fx[x].resize(sum+1); for(int i=hd[x],u;i;i=nxt[i]) { if(vis[u=to[i]])continue; int ns=(siz[u]>siz[x]?sum-siz[x]:siz[u]); mx=xn; getrt(u,0,ns); work(rt,ns); } } char dc[5]; void ins(int nw,int x,int v){w[nw]+=v; for(x=Min(x,t[nw].size()-1);x;x-=(x&-x))t[nw][x]+=v;}///w[nw] ll query(int nw,int x){/*if(x==0)return w[nw];*/ ll ret=0; for(;x<t[nw].size()&&x;x+=(x&-x))ret+=t[nw][x]; return ret;} void ins2(int nw,int x,int v){for(x=Min(x,fx[nw].size()-1);x;x-=(x&-x))fx[nw][x]+=v;} ll query2(int nw,int x){ll ret=0; for(;x<fx[nw].size()&&x;x+=(x&-x))ret+=fx[nw][x]; return ret;} ll ask(int x) { ll ret=0; for(int i=dep[x];i;i--) ret+=query(fa[x][i],dis[x][i])-(i==1?0:query2(fa[x][i],dis[x][i-1])); return ret+w[x]; } void change(int x,int d,int val) { for(int i=dep[x];i;i--) { //if(d<dis[x][i])continue; if(d>=dis[x][i])ins(fa[x][i],d-dis[x][i],val); if(d<dis[x][i-1]||i==1)continue; ins2(fa[x][i],d-dis[x][i-1],val);// } } int main() { n=rd(); int m=rd(); for(int i=1,x,y;i<n;i++)x=rd(),y=rd(),add(x,y),add(y,x); mx=xn; getrt(1,0,n); work(rt,n); for(int i=1;i<=n;i++)fa[i][++dep[i]]=i; for(int i=1,x,d,val;i<=m;i++) { scanf("%s",dc+1); x=rd(); if(dc[1]=='Q')printf("%lld ",ask(x)); else d=rd(),val=rd(),change(x,d,val); } return 0; }