题目地址：洛谷：【P2590】[ZJOI2008]树的统计 – 洛谷、BZOJ：Problem 1036. — [ZJOI2008]树的统计Count

题目描述

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。
我们将以下面的形式来要求你对这棵树完成一些操作：
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
III. QSUM u v: 询问从点u到点v的路径上的节点的权值和
注意：从点u到点v的路径上的节点包括u和v本身

输入输出格式

输入格式：
输入文件的第一行为一个整数n，表示节点的个数。
接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。
接下来一行n个整数，第i个整数wi表示节点i的权值。
接下来1行，为一个整数q，表示操作的总数。
接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。

输出格式：
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

输入输出样例

输入样例#1：

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

输出样例#1：

4
1
2
2
10
6
5
6
5
16

说明

对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

题解

比洛谷树剖模板还简单。就是个裸树剖。

代码

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

#include <algorithm>
#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;
}

inline bool isop(char c) {
    return c == 'X' || c == 'S' || c == 'C';
}

inline char readop() {
    char c;
    while(!isop(c = fgc()));
    return c;
}

const int MAXN = 30005, INF = 1e9;

int n, q, dfn[MAXN], ptn[MAXN], w[MAXN];
std::vector<int> gra[MAXN];

#define lch o << 1
#define rch (o << 1) | 1
#define mid ((l + r) >> 1)

LL val[MAXN << 2], mx[MAXN << 2];

inline void merge(int o) {
    val[o] = val[lch] + val[rch];
    mx[o] = std::max(mx[lch], mx[rch]);
}

inline void build(int o, int l, int r) {
    if(l == r) {
        val[o] = mx[o] = w[ptn[l]];
        return;
    }
    build(lch, l, mid);
    build(rch, mid + 1, r);
    merge(o);
}

inline void modify(int o, int l, int r, int x, LL v) {
    if(l == r) {
        val[o] = mx[o] = v;
        return;
    }
    if(x <= mid) modify(lch, l, mid, x, v);
    else modify(rch, mid + 1, r, x, v);
    merge(o);
}

inline LL querys(int o, int l, int r, int ll, int rr) {
    if(l >= ll && r <= rr) {
        return val[o];
    }
    LL res = 0;
    if(ll <= mid) res += querys(lch, l, mid, ll, rr);
    if(rr > mid) res += querys(rch, mid + 1, r, ll, rr);
    return res;
}
inline LL querym(int o, int l, int r, int ll, int rr) {
    if(l >= ll && r <= rr) {
        return mx[o];
    }
    LL res = -INF;
    if(ll <= mid) res = std::max(res, querym(lch, l, mid, ll, rr));
    if(rr > mid) res = std::max(res, querym(rch, mid + 1, r, ll, rr));
    return res;
}

int fa[MAXN], siz[MAXN], dep[MAXN], top[MAXN], son[MAXN], clk;

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

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

inline LL querys(int x, int y) {
    int tx = top[x], ty = top[y];
    LL res = 0;
    while(tx != ty) {
        if(dep[tx] > dep[ty]) {
            std::swap(x, y);
            std::swap(tx, ty);
        }
        res += querys(1, 1, n, dfn[ty], dfn[y]);
        y = fa[ty];
        ty = top[y];
    }
    if(dep[x] > dep[y]) {
        std::swap(x, y);
    }
    res += querys(1, 1, n, dfn[x], dfn[y]);
    return res;
}

inline LL querym(int x, int y) {
    int tx = top[x], ty = top[y];
    LL res = -INF;
    while(tx != ty) {
        if(dep[tx] > dep[ty]) {
            std::swap(x, y);
            std::swap(tx, ty);
        }
        res = std::max(res, querym(1, 1, n, dfn[ty], dfn[y]));
        y = fa[ty];
        ty = top[y];
    }
    if(dep[x] > dep[y]) {
        std::swap(x, y);
    }
    res = std::max(res, querym(1, 1, n, dfn[x], dfn[y]));
    return res;
}

inline void modify(int x, LL z) {
    modify(1, 1, n, dfn[x], z);
}

int x, y;
char op;

int main() {
    n = readint();
    for(int i = 1; i < n; i++) {
        x = readint(); y = readint();
        gra[x].push_back(y);
        gra[y].push_back(x);
    }
    for(int i = 1; i <= n; i++) w[i] = readint();
    dfs1(1);
    dfs2(1, 1);
    build(1, 1, n);
    q = readint();
    while(q--) {
        op = readop(); x = readint(); y = readint();
        if(op == 'X') {
            printf("%lld\n", querym(x, y));
        } else if(op == 'S') {
            printf("%lld\n", querys(x, y));
        } else {
            modify(x, y);
        }
    }
    return 0;
}