树剖模板+1 记得开long long
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define maxn 100010 using namespace std; struct node { int ed,nxt; }; node edge[maxn<<1]; int n,m,first[maxn],cnt; int fa[maxn],siz[maxn],son[maxn],dep[maxn]; int rnk[maxn],seg[maxn],top[maxn],rnk_cnt; long long tree[maxn<<2],tag[maxn<<2],ans,tot; inline void add_edge(int s,int e) { ++cnt; edge[cnt].ed=e; edge[cnt].nxt=first[s]; first[s]=cnt; return; } inline void dfs_1(int now,int pre) { dep[now]=dep[pre]+1; fa[now]=pre; siz[now]=1; for(register int i=first[now];i;i=edge[i].nxt) { int e=edge[i].ed; if(e==fa[now]) continue; dfs_1(e,now); siz[now]+=siz[e]; if(son[now]==-1||siz[e]>siz[son[now]]) son[now]=e; } return; } inline void dfs_2(int now,int heavy_fa) { top[now]=heavy_fa; ++rnk_cnt; rnk[now]=rnk_cnt; seg[rnk_cnt]=now; if(son[now]==-1) return; dfs_2(son[now],heavy_fa); for(register int i=first[now];i;i=edge[i].nxt) { int e=edge[i].ed; if(e!=fa[now]&&e!=son[now]) dfs_2(e,e); } return; } inline void push_down(int k,int l,int r) { int mid=(l+r)>>1,son=k<<1; tree[son]=(tree[son]+(mid-l+1)*tag[k]); tag[son]=(tag[son]+tag[k]); tree[son|1]=(tree[son|1]+(r-mid)*tag[k]); tag[son|1]=(tag[son|1]+tag[k]); tag[k]=0; return; } inline void modify(int k,int l,int r,int x,int y,int v) { if(r<x||l>y) return; if(x<=l&&r<=y) { tree[k]=(tree[k]+v*(r-l+1)); tag[k]=(tag[k]+v); return; } if(tag[k]) push_down(k,l,r); int mid=(l+r)>>1,son=k<<1; modify(son,l,mid,x,y,v); modify(son|1,mid+1,r,x,y,v); tree[k]=(tree[son]+tree[son|1]); return; } inline void modify_tree(int x,int y,int v) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); modify(1,1,n,rnk[top[x]],rnk[x],v); x=fa[top[x]]; } modify(1,1,n,min(rnk[x],rnk[y]),max(rnk[x],rnk[y]),v); return; } inline void get_sum(int k,int l,int r,int x,int y) { if(r<x||l>y) return; if(x<=l&&r<=y) { tot+=tree[k]; return; } if(tag[k]) push_down(k,l,r); int mid=(l+r)>>1,son=k<<1; get_sum(son,l,mid,x,y); get_sum(son|1,mid+1,r,x,y); tree[k]=tree[son]+tree[son|1]; return; } int main() { scanf("%d",&n); for(register int i=1;i<=n-1;++i) { int s,e; scanf("%d%d",&s,&e); add_edge(s+1,e+1); add_edge(e+1,s+1); } memset(son,-1,sizeof(son)); dfs_1(1,0); dfs_2(1,1); scanf("%d",&m); for(register int i=1;i<=m;++i) { char opt; cin>>opt; if(opt=='A') { int x,y,v; scanf("%d%d%d",&x,&y,&v); modify_tree(x+1,y+1,v); } else { tot=0; int x; scanf("%d",&x); x++; get_sum(1,1,n,rnk[x],rnk[x]+siz[x]-1); printf("%lld ",tot); } } return 0; }