蒟蒻树剖求调2333

#include<bits/stdc++.h>
#define lson k << 1
#define rson k << 1 | 1
#define int long long
typedef long long LL;
const int N = 1e5+7;
using namespace std;
int n,q,en,head[N];
int hson[N],fat[N],siz[N],dep[N];
int top[N],seg[N],id[N]; 
int tree[N << 2],lazy[N << 2];
struct Edge{
	int to,next;
}edge[N << 1];
inline void read(LL &x){
	char ch,last = ' ';
	while ((ch=getchar())<'0' || ch>'9') last = ch;
	for (x=0;ch>='0' && ch<='9';ch=getchar())
		x = x*10+ch-'0';
	if (last=='-') x = -x;
}
inline void add(LL x,LL y){
	edge[++en].to = y;
	edge[en].next = head[x];
	head[x] = en;
}
void init(){
	read(n);
	for(int i=1;i<n;i++){
		int a,b;
		read(a);read(b);
		add(a+1,b+1);
		add(b+1,a+1);
	}
}

void dfs1(int u,int fa){
	fat[u] = fa;
	dep[u] = dep[fa]+1;
	siz[u] = 1;
	for(int i=head[u];i;i=edge[i].next ){
		int v=edge[i].to;
		if(v!=fat[u]){
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[v]>siz[hson[u]]) hson[u] = v;
		}
	}
}
void dfs2(int u,int Top){
	seg[0]++;
	id[u] = seg[0];
	seg[seg[0]] = u;
	top[u] = Top;
	if(!hson[u]) return;
	dfs2(hson[u],Top);
	for(int i=head[u];i;i=edge[i].next){
		int v = edge[i].to ;
		if(!top[v])
			dfs2(v,v);			
	}
}
void pushup(int k){
	tree[k] = tree[lson] + tree[rson];
}
void pushdown(int k,int l,int r){
	if(lazy[k]){
		int mid = (l+r)/2;
		tree[lson] = tree[lson]+(mid-l+1)*lazy[k];
		lazy[lson] = lazy[lson]+lazy[k];
	
		tree[rson] = tree[rson]+(r-mid)*lazy[k];
		lazy[rson] = lazy[rson]+lazy[k];
	
		lazy[k] = 0;		
	}

}

void update(int k,int l,int r,int x,int y,int d){
	if(l>y || r<x) return;
	if(x<=l && r<=y){
		tree[k] = tree[k]+(r-l+1)*d;
		lazy[k] = lazy[k]+d;
		return;
	}
	pushdown(k,l,r);
	int mid = (l+r)/2;
	update(lson,l,mid,x,y,d);
	update(rson,mid+1,r,x,y,d);
	pushup(k);
}
void jia(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,id[top[x]],id[x],z);
		x = fat[top[x]];
	}
	if (dep[x]>dep[y]) swap(x,y);
	update(1,1,n,id[x],id[y],z);
}

int query(int k,int l,int r,int x,int y){
	if(l>y || r<x) return 0;
	if(x<=l && r<=y) return tree[k];
	pushdown(k,l,r);
	int mid = (l+r)/2;
	return query(lson,l,mid,x,y) + query(rson,mid+1,r,x,y);
}

void solve(){
	scanf("%lld",&q);
	 for (int i=1;i<=q;i++){
        int u,v,d;
        
        char c;
        scanf("%s",&c);
        if (c=='A'){
            scanf("%lld%lld%lld",&u,&v,&d);
            jia(u+1,v+1,d);
        }
        else{
            scanf("%lld",&u);
            printf("%lld\n",query(1,1,n,seg[u+1],seg[u + 1] + siz[u + 1] - 1));
        }
    }
}

signed main(){
	init();
	dfs1(1,0);
	dfs2(1,1);
	solve();
	return 0;
}