[shoi2012]魔法树(代码片段)

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
typedef long long LL;

struct edge

    int to , nxt;
 e[MAXN << 1];

int n , tot , timer;
int head[MAXN] , size[MAXN] , son[MAXN]  , fa[MAXN] , dfn[MAXN] , depth[MAXN] , top[MAXN];

template <typename T> inline void chkmax(T &x , T y)  x = max(x , y); 
template <typename T> inline void chkmin(T &x , T y)  x = min(x , y); 
template <typename T> inline void read(T &x)

    T f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -f;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - ‘0‘;
    x *= f;

struct Segment_Tree

    struct Node
    
        int l , r;
        LL sum , tag;
     Tree[MAXN << 2];
    inline void build(int index , int l , int r)
    
        Tree[index].l = l;
        Tree[index].r = r;
        Tree[index].tag = Tree[index].sum = 0;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(index << 1 , l , mid);
        build(index << 1 | 1 , mid + 1 , r);
    
    inline void pushdown(int index)
    
        int l = Tree[index].l , r = Tree[index].r;
        int mid = (l + r) >> 1;
        Tree[index << 1].sum += (mid - l + 1) * Tree[index].tag;
        Tree[index << 1 | 1].sum += (r - mid) * Tree[index].tag;
        Tree[index << 1].tag += Tree[index].tag;
        Tree[index << 1 | 1].tag += Tree[index].tag;
        Tree[index].tag = 0;
    
    inline void update(int index)
    
        Tree[index].sum = Tree[index << 1].sum + Tree[index << 1 | 1].sum;
    
    inline void modify(int index , int l , int r , LL value)
    
        if (Tree[index].l == l && Tree[index].r == r)
        
            Tree[index].sum += value * (r - l + 1);
            Tree[index].tag += value;
            return;
        
        pushdown(index);
        int mid = (Tree[index].l + Tree[index].r) >> 1;
        if (mid >= r) modify(index << 1 , l , r , value);
        else if (mid + 1 <= l) modify(index << 1 | 1 , l , r , value);
        else
        
            modify(index << 1 , l , mid , value);
            modify(index << 1 | 1 , mid + 1 , r , value);
         
        update(index); 
    
    inline LL query(int index , int l , int r)
    
        if (Tree[index].l == l && Tree[index].r == r) return Tree[index].sum;
        pushdown(index);
        int mid = (Tree[index].l + Tree[index].r) >> 1;
        if (mid >= r) return query(index << 1 , l , r);
        else if (mid + 1 <= l) return query(index << 1 | 1 , l , r);
        else return query(index << 1 , l , mid) + query(index << 1 | 1 , mid + 1 , r);
    
 SGT;
inline void addedge(int u , int v)

    ++tot;
    e[tot] = (edge)v , head[u];
    head[u] = tot;
 
inline void dfs1(int u)

    son[u] = -1;
    size[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt)
    
        int v = e[i].to;
        if (v == fa[u]) continue;
        fa[v] = u;
        depth[v] = depth[u] + 1;
        dfs1(v);
        size[u] += size[v];
        if (son[u] == -1 || size[v] > size[son[u]]) son[u] = v;
    

inline void dfs2(int u , int tp)

    dfn[u] = ++timer;
    top[u] = tp;
    if (son[u] != -1) dfs2(son[u] , tp);
    for (int i = head[u]; i; i = e[i].nxt)
    
        int v = e[i].to;
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v , v);
    

inline void modify(int u , int v , LL d)

    int tu = top[u] , tv = top[v];
    while (tu != tv)
    
        if (depth[tu] > depth[tv])
        
            swap(u , v);
            swap(tu , tv);
            
        SGT.modify(1 , dfn[tv] , dfn[v] , d);
        v = fa[tv]; tv = top[v];
        
    if (depth[u] > depth[v]) swap(u , v);
    SGT.modify(1, dfn[u] , dfn[v] , d);


int main()

    
    scanf("%d" , &n);
    for (int i = 1; i < n; i++)
    
        int u , v;
        scanf("%d%d" , &u , &v);
        addedge(u , v);    
        fa[v] = u;
    
    dfs1(0);
    dfs2(0 , 0);
    SGT.build(1 , 1 , n);
    int q;
    scanf("%d" , &q);
    while (q--)
    
        char op[5];
        scanf("%s" , &op);
        if (op[0] == ‘A‘)
        
            int u , v;
            LL d;
            scanf("%d%d%lld" , &u , &v , &d);
            modify(u , v , d);
         else
        
            int u;
            scanf("%d" , &u);
            printf("%lld
" , SGT.query(1 , dfn[u] , dfn[u] + size[u] - 1));
        
    
    
    return 0;