有两个操作：
- 将 \(u\) 到 \(v\) 路径增加 \(k\)
- 询问 \(u\) 节点的子树和
显然，我们可以用树链剖分+线段树来做。
代码：
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<algorithm>
typedef long long LL;
typedef unsigned long long ULL;
namespace FastIo{
typedef __uint128_t ULLL;
static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw;
#define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
inline void pc(const char &ch){
if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw;
*pw++=ch;
}
#define fsh fwrite(fw,1,pw-fw,stdout),pw=fw
struct FastMod{
FastMod(ULL b):b(b),m(ULL((ULLL(1)<<64)/b)){}
ULL reduce(ULL a){
ULL q=(ULL)((ULLL(m)*a)>>64);
ULL r=a-q*b;
return r>=b?r-b:r;
}
ULL b,m;
}HPOP(10);
struct QIO{
char ch;
int st[40];
inline void read(int &x){
x=0,ch=gc;
while(!isdigit(ch))ch=gc;
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
}
inline char read(){
ch=gc;
while(ch<'A'||ch>'Z')ch=gc;
return ch;
}
template<class T>inline void write(T a){
do{st[++st[0]]=HPOP.reduce(a);a/=10;}while(a);
while(st[0])pc(st[st[0]--]^48);
pc('\n');
}
}qrw;
}
using namespace FastIo;
#define NUMBER1 100000
#define P(A) A=-~A
#define fione_i(begin,end) for(register int i=begin;i<=end;P(i))
#define tt(u) for(register int i=head[u];i;i=e[i].next)
#define ls(rt) rt<<1
#define rs(rt) rt<<1|1
#define mid (l+r>>1)
#define lson l,mid,ls(rt)
#define rson mid+1,r,rs(rt)
#define sz (r-l+1)
using std::swap;
struct EDGE{int next,to;}e[(NUMBER1<<1)+5];
int head[NUMBER1+5],n,cnt(0),tot(0),size[NUMBER1+5],top[NUMBER1+5],depth[NUMBER1+5],son[NUMBER1+5],fa[NUMBER1+5],id[NUMBER1+5];
inline void add(const int &u,const int &v){e[++tot].next=head[u];head[u]=tot,e[tot].to=v;}
struct Segment{//线段树
LL tree[(NUMBER1<<2)+5],lazy[(NUMBER1<<2)+5];
inline void push_up(const int &rt){tree[rt]=tree[ls(rt)]+tree[rs(rt)];}
inline void change(int l,int r,int rt,LL date){tree[rt]+=date*sz,lazy[rt]+=date;}
inline void push_down(int l,int r,int rt){
change(lson,lazy[rt]);change(rson,lazy[rt]);
lazy[rt]=0;
}
void intervaland(int l,int r,int rt,int x,int y,LL date){
if(x<=l&&r<=y)return tree[rt]+=date*sz,lazy[rt]+=date,void();
push_down(l,r,rt);
if(x<=mid)intervaland(lson,x,y,date);
if(mid<y)intervaland(rson,x,y,date);
push_up(rt);
}
LL intervalsum(int l,int r,int rt,int x,int y){
if(x<=l&&r<=y)return tree[rt];
push_down(l,r,rt);
LL res(0);
if(x<=mid)res+=intervalsum(lson,x,y);
if(mid<y)res+=intervalsum(rson,x,y);
return res;
}
}seg;
void dfs1(int u,int fath,int deep){//树链剖分
size[u]=1,fa[u]=fath,depth[u]=deep;
int ms(-1);
tt(u){
if(e[i].to==fath)continue;
dfs1(e[i].to,u,deep+1);
size[u]+=size[e[i].to];
if(size[e[i].to]>ms)ms=size[e[i].to],son[u]=e[i].to;
}
}
void dfs2(int u,int tf){
id[u]=++cnt,top[u]=tf;
if(!son[u])return;
dfs2(son[u],tf);
tt(u){
if(e[i].to==fa[u]||e[i].to==son[u])continue;
dfs2(e[i].to,e[i].to);
}
}
inline void treeand(int x,int y,LL date){//路径和加k
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]])swap(x,y);
seg.intervaland(1,n,1,id[top[x]],id[x],date);
x=fa[top[x]];
}
if(depth[x]>depth[y])swap(x,y);
seg.intervaland(1,n,1,id[x],id[y],date);
}
signed main(){
char a;
int q,x,y,k;
qrw.read(n);
fione_i(2,n){
qrw.read(x);
qrw.read(y);
P(x),P(y);
add(x,y);add(y,x);
}
dfs1(1,0,1);
dfs2(1,1);
qrw.read(q);
while(q--){
a=qrw.read();
qrw.read(x);
P(x);
if(a=='A'){
qrw.read(y);
P(y);
qrw.read(k);
treeand(x,y,k);
}else qrw.write(seg.intervalsum(1,n,1,id[x],id[x]+size[x]-1));
}
fsh;
exit(0);
return 0;
}