题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2836
树剖裸题。然而WA、RE了好久……
原来是跳 top 的那个地方！ top 不相等的时候比较的是 top 的深度，不是自己的深度！ top 相等之后才比较自己的深度。
dfs 序离开自己时的标号就是 dfn[ cr ] + siz[ cr ] -1 。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=1e5+5; int n,q,hd[N],xnt,to[N],nxt[N]; int fa[N],dep[N],dfn[N],tim,siz[N],son[N],top[N]; int tot,ls[N<<1],rs[N<<1]; ll sm[N<<1],laz[N<<1];// char ch[10]; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return fx?ret:-ret; } void add(int x,int y) { to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt; } void dfs(int cr) { dep[cr]=dep[fa[cr]]+1; siz[cr]=1; for(int i=hd[cr],v;i;i=nxt[i]) { v=to[i]; dfs(v);siz[cr]+=siz[v]; siz[v]>siz[son[cr]]?son[cr]=v:0; } } void dfsx(int cr) { dfn[cr]=++tim; if(son[cr])top[son[cr]]=top[cr],dfsx(son[cr]); for(int i=hd[cr],v;i;i=nxt[i]) if((v=to[i])!=son[cr]) top[v]=v,dfsx(v); } void build(int l,int r,int cr) { if(l==r)return; int mid=l+r>>1; ls[cr]=++tot;build(l,mid,ls[cr]); rs[cr]=++tot;build(mid+1,r,rs[cr]); } void pshd(int cr,int l,int mid,int r) { if(!laz[cr])return; ll d=laz[cr]; laz[cr]=0; sm[ls[cr]]+=d*(mid-l+1);sm[rs[cr]]+=d*(r-mid); laz[ls[cr]]+=d;laz[rs[cr]]+=d; } void pshp(int cr){sm[cr]=sm[ls[cr]]+sm[rs[cr]];} void mdfy(int l,int r,int cr,int L,int R,int k) { if(l>=L&&r<=R){sm[cr]+=(ll)k*(r-l+1);laz[cr]+=k;return;} int mid=l+r>>1;pshd(cr,l,mid,r); if(L<=mid)mdfy(l,mid,ls[cr],L,R,k); if(mid<R)mdfy(mid+1,r,rs[cr],L,R,k); pshp(cr); } void mdfy(int x,int y,int k) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y);//dep[top]!!! mdfy(1,n,1,dfn[top[x]],dfn[x],k); x=fa[top[x]]; } if(dep[x]<dep[y])swap(x,y);// mdfy(1,n,1,dfn[y],dfn[x],k); } ll query(int l,int r,int cr,int L,int R) { if(l>=L&&r<=R)return sm[cr]; int mid=l+r>>1;pshd(cr,l,mid,r); if(R<=mid)return query(l,mid,ls[cr],L,R); if(mid<L)return query(mid+1,r,rs[cr],L,R); return query(l,mid,ls[cr],L,R)+query(mid+1,r,rs[cr],L,R); } int main() { n=rdn(); for(int i=1,u,v;i<n;i++) { u=rdn()+1; v=rdn()+1; fa[v]=u; add(u,v); } dfs(1); top[1]=1; dfsx(1); tot=1; build(1,n,1); int u,v,d;q=rdn(); while(q--) { scanf("%s",ch); if(ch[0]=='A') { u=rdn()+1; v=rdn()+1; d=rdn(); mdfy(u,v,d); } else { u=rdn()+1; printf("%lld ",query(1,n,1,dfn[u],dfn[u]+siz[u]-1));// } } return 0; }