题目：洛谷P3833。
题目大意：给你一棵树，有两种操作：1.给两个点和它们之间的最短路上的所有点加上一个值；2.询问以某个点为根的子树的子树和。你需要实现这个功能。
解题思路：如果只有最后才询问的话，本题可以用树上差分做。然而询问和修改是穿插的。
那么我们只能使用树链剖分了。
用树剖则很简单，修改就是边求lca边维护线段树。查询则是线段树区间查询。
由于本题从0开始编号，把每个点的编号+1，就变成从1开始编号（主要是因为习惯）。
时间复杂度$O(Qlog^2 n)$。
C++ Code：
#include<cstdio>
#include<cctype>
#include<cstring>
#define N 100005
#define ll long long
int n,head[N],cnt,sz[N],dep[N],son[N],top[N],fa[N],dfn[N],idx,t,L,R;
ll ans;
struct edge{
int to,nxt;
}e[N<<1];
struct SegmentTreeNode{
ll s,add;
}d[N<<2];
inline int readint(){
char c=getchar();
for(;!isdigit(c);c=getchar());
int d=0;
for(;isdigit(c);c=getchar())
d=(d<<3)+(d<<1)+(c^'0');
return d;
}
void dfs(int now){
sz[now]=1;
for(int i=head[now];i;i=e[i].nxt)
if(!dep[e[i].to]){
dep[e[i].to]=dep[now]+1;
fa[e[i].to]=now;
dfs(e[i].to);
sz[now]+=sz[e[i].to];
if(!son[now]||sz[son[now]]<sz[e[i].to])son[now]=e[i].to;
}
}
void dfs2(int now){
dfn[now]=++idx;
if(son[now])top[son[now]]=top[now],dfs2(son[now]);
for(int i=head[now];i;i=e[i].nxt)
if(e[i].to!=son[now]&&dep[now]<dep[e[i].to])
top[e[i].to]=e[i].to,dfs2(e[i].to);
}
inline void pushdown(int o,int len){
int ld=o<<1,rd=o<<1|1;
d[ld].add+=d[o].add;
d[ld].s+=d[o].add*((len+1)>>1);
d[rd].add+=d[o].add;
d[rd].s+=d[o].add*(len>>1);
d[o].add=0;
}
void addt(int l,int r,int o){
if(L<=l&&r<=R){
d[o].add+=t;
d[o].s+=(ll)t*(r-l+1);
}else{
pushdown(o,r-l+1);
int mid=(l+r)>>1;
if(L<=mid)addt(l,mid,o<<1);
if(mid<R)addt(mid+1,r,o<<1|1);
d[o].s=d[o<<1].s+d[o<<1|1].s;
}
}
void add(int x,int y){
for(;top[x]!=top[y];)
if(dep[top[x]]>=dep[top[y]]){
L=dfn[top[x]],R=dfn[x];
addt(1,n,1);
x=fa[top[x]];
}else{
L=dfn[top[y]],R=dfn[y];
addt(1,n,1);
y=fa[top[y]];
}
if(dep[x]<=dep[y])L=dfn[x],R=dfn[y];else
L=dfn[y],R=dfn[x];
addt(1,n,1);
}
void query(int l,int r,int o){
if(L<=l&&r<=R)ans+=d[o].s;else{
pushdown(o,r-l+1);
int mid=(l+r)>>1;
if(L<=mid)query(l,mid,o<<1);
if(mid<R)query(mid+1,r,o<<1|1);
}
}
int main(){
n=readint();
cnt=idx=0;
for(int i=1;i<n;++i){
int u=readint()+1,v=readint()+1;
e[++cnt]=(edge){v,head[u]};
head[u]=cnt;
e[++cnt]=(edge){u,head[v]};
head[v]=cnt;
}
dep[1]=top[1]=fa[1]=1;
dfs(1);dfs2(1);
memset(d,0,sizeof d);
for(int q=readint();q--;){
char c=getchar();
while(!isalpha(c))c=getchar();
if(c=='A'){
int x=readint()+1,y=readint()+1;t=readint();
add(x,y);
}else{
int u=readint()+1;
L=dfn[u],R=dfn[u]+sz[u]-1;
ans=0;
query(1,n,1);
printf("%lld
",ans);
}
}
return 0;
}