这道题告诉我们：树链剖分的重标号就是dfs序。
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100001
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
typedef long long ll;
ll delta[N<<2],sumv[N<<2];
int n,m;
int en,v[N],first[N],next[N];
void AddEdge(const int &U,const int &V)
{
v[++en]=V;
next[en]=first[U];
first[U]=en;
}
int dep[N],fa[N],siz[N],son[N],tot,Ls[N],top[N],Rs[N];
void dfs(int U)
{
siz[U]=1;
for(int i=first[U];i;i=next[i])
{
fa[v[i]]=U;
dep[v[i]]=dep[U]+1;
dfs(v[i]);
siz[U]+=siz[v[i]];
if(siz[son[U]]<siz[v[i]])
son[U]=v[i];
}
}
void dfs2(int U)
{
Ls[U]=++tot;
if(son[U])
{
top[son[U]]=top[U];
dfs2(son[U]);
}
for(int i=first[U];i;i=next[i])
if(v[i]!=son[U])
{
top[v[i]]=v[i];
dfs2(v[i]);
}
Rs[U]=tot;
}
void pushdown(int rt,int size)
{
if(delta[rt])
{
delta[rt<<1]+=delta[rt];
delta[rt<<1|1]+=delta[rt];
sumv[rt<<1]+=delta[rt]*(ll)(size-(size>>1));
sumv[rt<<1|1]+=delta[rt]*(ll)(size>>1);
delta[rt]=0;
}
}
void update(int ql,int qr,int v,int rt,int l,int r)
{
if(ql<=l&&r<=qr)
{
delta[rt]+=(ll)v;
sumv[rt]+=((ll)(r-l+1)*(ll)v);
return;
}
pushdown(rt,r-l+1);
int m=(l+r>>1);
if(ql<=m) update(ql,qr,v,lson);
if(m<qr) update(ql,qr,v,rson);
sumv[rt]=sumv[rt<<1]+sumv[rt<<1|1];
}
ll query(int ql,int qr,int rt,int l,int r)
{
if(ql<=l&&r<=qr) return sumv[rt];
pushdown(rt,r-l+1);
int m=(l+r>>1); ll res=0;
if(ql<=m) res+=query(ql,qr,lson);
if(m<qr) res+=query(ql,qr,rson);
return res;
}
void Update(int U,int V,int W)
{
int f1=top[U],f2=top[V];
while(f1!=f2)
{
if(dep[f1]<dep[f2])
{
swap(U,V);
swap(f1,f2);
}
update(Ls[f1],Ls[U],W,1,1,n);
U=fa[f1];
f1=top[U];
}
if(dep[U]>dep[V])
swap(U,V);
update(Ls[U],Ls[V],W,1,1,n);
}
int main()
{
int A,B,C; char op[2];
scanf("%d",&n);
for(int i=1;i<n;++i)
{
scanf("%d%d",&A,&B);
AddEdge(A+1,B+1);
}
top[1]=1;
dfs(1);
dfs2(1);
scanf("%d",&m);
for(;m;--m)
{
scanf("%s%d",op,&A);
if(op[0]=='A')
{
scanf("%d%d",&B,&C);
Update(A+1,B+1,C);
}
else
printf("%lld
",query(Ls[A+1],Rs[A+1],1,1,n));
}
return 0;
}