样例过,交上去爆零
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define ll long long
#define ls(x) x<<1
#define rs(x) x<<1|1
int n,q,cnt;
int u,v,d;
char ch;
vector<int>G[N];
int dep[N],fa[N],sz[N],top[N],rnk[N],dfn[N],son[N];
int siz[N];
ll w[N<<2],lzy[N<<2];
void dfs1(int u,int father){
dep[u]=dep[father]+1;
fa[u]=father;
sz[u]=1;
for(auto v:G[u]){
if(v==father){
continue;
}
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]]){
son[u]=v;
}
}
}
void dfs2(int u,int tp){
top[u]=tp,dfn[u]=++cnt;
rnk[dfn[u]]=u;
if(son[u]==0){
return;
}
dfs2(son[u],tp);
for(auto v:G[u]){
if(v!=fa[u]&&v!=son[u]){
dfs2(v,v);
}
}
}
void pushup(int u){
w[u]=w[ls(u)]+w[rs(u)];
}
void build(int u,int l,int r){
siz[u]=r-l+1;
if(l==r){
return;
}
int mid=l+r>>1;
build(ls(u),l,mid);
build(rs(u),mid+1,r);
pushup(u);
}
void pushdown(int u){
if(lzy[u]){
lzy[ls(u)]+=lzy[u];
lzy[rs(u)]+=lzy[u];
w[ls(u)]+=siz[ls(u)]*lzy[u];
w[rs(u)]+=siz[rs(u)]*lzy[u];
lzy[u]=0;
}
}
void update(int u,int l,int r,int L,int R,int p){
if(L<=l&&r<=R){
w[u]+=siz[u]*p;
lzy[u]+=p;
}
else if(!(R<l||r<L)){
pushdown(u);
int mid=l+r>>1;
update(ls(u),l,mid,L,R,p);
update(rs(u),mid+1,r,L,R,p);
pushup(u);
}
}
void modify(int x,int y,int z){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){
swap(x,y);
}
update(1,1,n,dfn[top[x]],dfn[x],z);
x=fa[top[x]];
}
if(dfn[x]>dfn[y]){
swap(x,y);
}
update(1,1,n,dfn[x],dfn[y],z);
}
ll qry(int u,int l,int r,int L,int R){
if(L<=l&&r<=R){
return w[u];
}
else if(!(R<l||r<L)){
pushdown(u);
int mid=l+r>>1;
return qry(ls(u),l,mid,L,R)+qry(rs(u),mid+1,r,L,R);
}
return 0;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n;
for(int i=1;i<n;i++){
cin>>u>>v;
u++,v++;
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(1,0);
dfs2(1,0);
build(1,1,n);
cin>>q;
while(q--){
cin>>ch;
if(ch=='A'){
cin>>u>>v>>d;
u++,v++;
modify(u,v,d);
}
else{
cin>>u; u++;
cout<<qry(1,1,n,dfn[u],dfn[u]+sz[u]-1)<<"\n";
}
}
return 0;
}