题目地址：洛谷：【P3178】[HAOI2015]树上操作 – 洛谷、BZOJ：Problem 4034. — [HAOI2015]树上操作

题目描述

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

输入输出格式

输入格式：
第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1 行每行两个正整数 from, to ， 表示该树中存在一条边 (from, to) 。再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。

输出格式：
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

输入输出样例

输入样例#1：

5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3

输出样例#1：

6
9
13

说明

对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。

题解

比树剖那篇文章的例题还裸。

代码

 // Code by KSkun, 2018/3
#include <cstdio>

#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

int n, m, w[MAXN], ut, vt, op, xt, at;
int fa[MAXN], siz[MAXN], son[MAXN], dfn[MAXN], ptn[MAXN], top[MAXN], dep[MAXN], cnt;
std::vector<int> gra[MAXN];

inline void addedge(int u, int v) {
    gra[u].push_back(v);
    gra[v].push_back(u);
}

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

inline void dfs2(int u, int tp) {
    top[u] = tp;
    dfn[u] = ++cnt;
    ptn[dfn[u]] = u;
    if(son[u]) dfs2(son[u], tp);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

struct Node {
    LL val, add;
} sgt[MAXN << 2];

inline void pushdown(int o, int l, int r) {
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    if(sgt[o].add) {
        sgt[lch].add += sgt[o].add;
        sgt[rch].add += sgt[o].add;
        sgt[lch].val += sgt[o].add * (mid - l + 1);
        sgt[rch].val += sgt[o].add * (r - mid);
        sgt[o].add = 0;
    }
}

inline void build(int o, int l, int r) {
    if(l == r) {
        sgt[o].val = w[ptn[l]];
        return;
    }
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    build(lch, l, mid);
    build(rch, mid + 1, r);
    sgt[o].val = sgt[lch].val + sgt[rch].val;
}

inline void add(int o, int l, int r, int ll, int rr, LL v) {
    if(l >= ll && r <= rr) {
        sgt[o].add += v;
        sgt[o].val += v * (r - l + 1);
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    if(ll <= mid) add(lch, l, mid, ll, rr, v);
    if(rr > mid) add(rch, mid + 1, r, ll, rr, v);
    sgt[o].val = sgt[lch].val + sgt[rch].val;
}

inline LL query(int o, int l, int r, int ll, int rr) {
    if(l >= ll && r <= rr) {
        return sgt[o].val;
    }
    pushdown(o, l, r);
    LL res = 0;
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    if(ll <= mid) res += query(lch, l, mid, ll, rr);
    if(rr > mid) res += query(rch, mid + 1, r, ll, rr);
    return res;
}

inline void addpoint(int x, LL v) {
    add(1, 1, n, dfn[x], dfn[x], v);
}

inline void addsubtree(int x, LL v) {
    add(1, 1, n, dfn[x], dfn[x] + siz[x], v);
}

inline LL querychain(int x) {
    int tp = top[x];
    LL res = 0;
    while(x) {
        res += query(1, 1, n, dfn[tp], dfn[x]);
        x = fa[tp];
        tp = top[x];
    }
    return res;
}

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) w[i] = readint();
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint();
        addedge(ut, vt);
    }
    dfs1(1);
    dfs2(1, 1);
    build(1, 1, n);
    while(m--) {
        op = readint();
        xt = readint();
        if(op != 3) at = readint();
        if(op == 1) {
            addpoint(xt, at);
        }
        if(op == 2) {
            addsubtree(xt, at);
        }
        if(op == 3) {
            printf("%lld\n", querychain(xt));
        }
    }
    return 0;
}