题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2836
树链剖分裸题；
写码五分钟，调码两小时，RE不断，狂交二十五遍，终于找到一处小细节——易错点！
就是跳 top 时，不是按 dep[x] < dep[y] 交换 x,y，而要按 dep[top[x]] < dep[top[y]] 交换 x,y，否则就跳不到 lca 了！
经验++。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid ((l+r)>>1)
#define ls (x<<1)
#define rs (x<<1|1)
using namespace std;
typedef long long ll;
int const xn=;
int n,fa[xn],hd[xn],ct,nxt[xn],to[xn],dfn[xn],tim,siz[xn],son[xn],top[xn],dep[xn];
ll sum[xn<<],lzy[xn<<];
char ch[];
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();
return f?ret:-ret;
}
void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}
void dfs(int x)
{
siz[x]=; dep[x]=dep[fa[x]]+;
for(int i=hd[x],u;i;i=nxt[i])
{
dfs(u=to[i]);
if(siz[u]>siz[son[x]])son[x]=u;
siz[x]+=siz[u];
}
}
void dfs2(int x)
{
dfn[x]=++tim;
if(son[x])top[son[x]]=top[x],dfs2(son[x]);
for(int i=hd[x],u;i;i=nxt[i])
{
if((u=to[i])==son[x])continue;
top[u]=u; dfs2(u);
}
// ed[x]=tim;
}
void pushdown(int x,int l,int r)
{
if(!lzy[x])return;
sum[ls]+=lzy[x]*(mid-l+); lzy[ls]+=lzy[x];
sum[rs]+=lzy[x]*(r-mid); lzy[rs]+=lzy[x];
lzy[x]=;
}
void update(int x,int l,int r,int L,int R,int k)
{
if(l>=L&&r<=R){sum[x]+=(ll)k*(r-l+); lzy[x]+=k; return;}
pushdown(x,l,r);
if(mid>=L)update(ls,l,mid,L,R,k);
if(mid<R)update(rs,mid+,r,L,R,k);
sum[x]=sum[ls]+sum[rs];
}
ll query(int x,int l,int r,int L,int R)
{
if(l>=L&&r<=R)return sum[x];
pushdown(x,l,r); ll ret=;
if(mid>=L)ret+=query(ls,l,mid,L,R);
if(mid<R)ret+=query(rs,mid+,r,L,R);
return ret;
}
void add(int x,int y,int d)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);//!!!!!
update(,,n,dfn[top[x]],dfn[x],d); x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
update(,,n,dfn[y],dfn[x],d);
}
int main()
{
n=rd();
for(int i=,x,y;i<n;i++)
{
x=rd()+; y=rd()+;
fa[y]=x; add(x,y);
}
dfs(); top[]=; dfs2();
int q=rd();
for(int i=,u,v,d;i<=q;i++)
{
scanf("%s",ch);
if(ch[]=='A')
{
u=rd()+; v=rd()+; d=rd();
add(u,v,d);
}
else u=rd()+,printf("%lld\n",query(,,n,dfn[u],dfn[u]+siz[u]-));
}
return ;
}