题意:区间+,子树求和

解法:树剖维护一颗线段树,子树求和用DFS序即可。

///BZOJ 2836

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int n, m, edgecnt, tim, siz[maxn], top[maxn], son[maxn], dep[maxn], tid[maxn], fa[maxn], head[maxn], L[maxn], R[maxn];
typedef long long LL;
struct edge{
    int v, next;
}E[maxn*2];
struct seg{
    int l,r;
    LL sum, lazy;
}tree[maxn*4];
void init(){
    memset(head, -1, sizeof(head));
    memset(son, -1, sizeof(son));
    edgecnt=tim=0;
}
void addedge(int u, int v){
    E[edgecnt].v=v,E[edgecnt].next=head[u],head[u]=edgecnt++;
}
void dfs1(int u, int father, int d){
    dep[u]=d;
    fa[u]=father;
    siz[u]=1;
    for(int i=head[u];~i;i=E[i].next){
        int v=E[i].v;
        if(v==father) continue;
        dfs1(v,u,d+1);
        siz[u]+=siz[v];
        if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs2(int u, int tp){
    top[u]=tp;
    L[u]=tid[u]=++tim;
    R[u]=tim;
    if(son[u]==-1) return;
    dfs2(son[u],tp);
    for(int i=head[u];~i;i=E[i].next){
        int v=E[i].v;
        if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
    }
    R[u]=tim;
}
void pushup(int rt){
    tree[rt].sum=tree[rt*2].sum+tree[rt*2+1].sum;
}
void pushdown(int rt){
    if(tree[rt].lazy){
        int mid=(tree[rt].l+tree[rt].r)/2;
        tree[rt*2].sum+=tree[rt].lazy*(LL)(mid-tree[rt].l+1);
        tree[rt*2].lazy+=tree[rt].lazy;
        tree[rt*2+1].sum+=tree[rt].lazy*(LL)(tree[rt].r-mid);
        tree[rt*2+1].lazy+=tree[rt].lazy;
        tree[rt].lazy=0;
    }
}
void build(int l, int r, int rt){
    tree[rt].l=l,tree[rt].r=r,tree[rt].sum=tree[rt].lazy=0;
    if(l==r) return;
    int mid=(l+r)/2;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
    pushup(rt);
}
void update(int L, int R, LL v, int rt){
    if(L<=tree[rt].l&&tree[rt].r<=R){
        tree[rt].lazy+=v;
        tree[rt].sum+=v*(LL)(tree[rt].r-tree[rt].l+1);
        return;
    }
    pushdown(rt);
    int mid=(tree[rt].l+tree[rt].r)/2;
    if(L<=mid) update(L,R,v,rt*2);
    if(mid<R) update(L,R,v,rt*2+1);
    pushup(rt);
}
LL query(int L, int R, int rt){
    if(L<=tree[rt].l&&tree[rt].r<=R){
        return tree[rt].sum;
    }
    pushdown(rt);
    int mid=(tree[rt].l+tree[rt].r)/2;
    LL ans = 0;
    if(L<=mid) ans+=query(L,R,rt*2);
    if(mid<R) ans+=query(L,R,rt*2+1);
    return ans;
}
void change(int u, int v, LL c){
    int f1=top[u],f2=top[v];
    while(f1!=f2){
        if(dep[f1]<dep[f2]) swap(f1,f2),swap(u,v);
        update(tid[f1],tid[u],c,1);
        u=fa[f1];
        f1=top[u];
    }
    if(dep[u]>dep[v]) swap(u,v);
    update(tid[u],tid[v],c,1);
}
int main()
{
    scanf("%d", &n);
    init();
    for(int i=1; i<n; i++){
        int u,v;
        scanf("%d%d", &u,&v);
        u++;v++;
        addedge(u,v);
        addedge(v,u);
    }
    dfs1(1,1,1);
    dfs2(1,1);
    build(1,n,1);
    scanf("%d", &m);
    while(m--){
        char op[10];
        scanf("%s", op);
        int x, y;
        LL c;
        if(op[0]=='A'){
            scanf("%d%d%lld", &x,&y,&c);
            x++;
            y++;
            change(x,y,c);
        }
        else{
            scanf("%d", &x);
            ++x;
            printf("%lld\n", query(L[x],R[x],1));
        }
    }
    return 0;
}

/* 5 0 1 1 2 1 3 0 4 */