洛谷【P3833】树链剖分线段树区间操作

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int maxm = maxn << 1;
///图(链式前向星出了点问题)
vector<int> g[maxm];
///线段树
struct node{
    int l, r, len;
    ll sum, lazy;
    int mid(){
        return (l + r) >> 1;
    }
}tree[maxn << 2];
///全局变量
int fa[maxn], dep[maxn], siz[maxn], son[maxn];///dfs1
int tim, dfn[maxn], top[maxn], w[maxn], val[maxn];///dfs2


void dfs1(int u, int f){
    fa[u] = f;
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    int maxsize = -1;
    for(int i = 0; i < g[u].size(); i++){
        int v = g[u][i];
        if(v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v] > maxsize){
            maxsize = siz[v];
            son[u] = v;
        }
    }
}

void dfs2(int u, int t){
    dfn[u] = ++tim;
    top[u] = t;
    w[tim] = u;
    if(!son[u]) return;
    dfs2(son[u], t);
    for(int i = 0; i < g[u].size(); i++){
        int v = g[u][i];
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

inline void PushDown(int root){
    if(tree[root].lazy){
        tree[root << 1].lazy += tree[root].lazy;
        tree[root << 1 | 1].lazy += tree[root].lazy;
        tree[root << 1].sum += tree[root].lazy * tree[root << 1].len;
        tree[root << 1 | 1].sum += tree[root].lazy * tree[root << 1 | 1].len;
        tree[root].lazy = 0;
    }
}

inline void PushUp(int root){
    tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
}

void Build(int root, int l, int r){
    tree[root].len = r - l + 1;
    tree[root].lazy = 0;
    tree[root].sum = 0;
    tree[root].l = l;
    tree[root].r = r;
    if(l == r){
        tree[root].sum = val[w[l]];
        return;
    }
    int mid = tree[root].mid();
    Build(root << 1, l, mid);
    Build(root << 1 | 1, mid + 1, r);
    PushUp(root);
}

void UpDate(int root, int l, int r, int c){
    if(tree[root].l >= l && r >= tree[root].r){
        tree[root].lazy += c;
        tree[root].sum += c * tree[root].len;
        return;
    }
    if(tree[root].l == tree[root].r) return;
    PushDown(root);
    int mid = tree[root].mid();
    if(r <= mid) UpDate(root << 1, l, r, c);
    else if(l > mid) UpDate(root << 1 | 1, l, r, c);
    else{
        UpDate(root << 1, l, mid, c);
        UpDate(root << 1 | 1, mid + 1, r, c);
    }
    PushUp(root);
}

ll Query(int root, int l, int r){
    if(tree[root].l >= l && r >= tree[root].r) return tree[root].sum;
    PushDown(root);
    int mid = tree[root].mid();
    if(r <= mid) return Query(root << 1, l, r);
    else if(l > mid) return Query(root << 1 | 1, l, r);
    else return Query(root << 1, l, mid) + Query(root << 1 | 1, mid + 1, r);
}

inline void mson(int x, int z){
    UpDate(1, dfn[x], dfn[x] + siz[x] - 1, z);
}

inline ll qson(int x){
    return Query(1, dfn[x], dfn[x] + siz[x] - 1);
}

inline void ChangeLink(int x, int y, int z){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        UpDate(1, dfn[top[x]], dfn[x], z);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    UpDate(1, dfn[x], dfn[y], z);
}

inline ll QueryLink(int x, int y){
    ll res = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        res += Query(1, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    res += Query(1, dfn[x], dfn[y]);
    return res;
}

int main(){
    int n, u, v, x, y, z, m;
    char s[10];
    scanf("%d", &n);
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        g[u + 1].push_back(v + 1);
        g[v + 1].push_back(u + 1);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    Build(1, 1, tim);
    scanf("%d", &m);
    getchar();
    for(int i = 1; i <= m; i++){
        scanf("%s", s);
        if(s[0] == 'A'){
            scanf("%d%d%d", &x, &y, &z);
            ChangeLink(x + 1, y + 1, z);
        }
        else{
            scanf("%d", &x);
            printf("%lld\n", qson(x + 1));
        }
    }

    return 0;
}