思路与算法

把树以1为根，先迭代求父亲、深度和遍历顺序，再逆序求子树大小与重儿子。沿重边优先编号，记录每条重链的链头和每点在线性序列中的位置。

在线性序列上建立线段树，每个区间保存节点权值的和与最大值。CHANGE对对应位置做单点赋值。

查询u-v路径时，只要链头不同，就取链头更深的一侧，把链头到该点的连续编号区间合并进答案，再跳到链头父亲。两点进入同一条链后，查询其间最后一个区间。QSUM累加各段和，QMAX取各段最大值。

正确性说明

重链中的节点按深度连续编号，因此链上两点之间的路径等于一个序列区间。链头不同的时候，较深链头到对应端点的整段都位于原查询路径上；移除这一段并上跳到链头父亲，不会漏掉路径节点，也不会重复计入节点。

不断移除这些段，直到剩下同链的最后一段，各段恰好构成完整u-v路径。线段树维护的区间和与最大值对单点赋值始终正确，合并所有互不重叠的路径段便得到所求统计。

复杂度

n点、q次操作。邻接表及所有剖分数组初始化O(n)，两遍迭代剖分O(n)，线段树数组初始化与建树O(n)。每次单点赋值O(log(n+1))；一条路径至多拆成O(log(n+1))段，每段查询O(log(n+1))，故路径查询O(log²(n+1))。总时间O(n+q log²(n+1))，空间O(n)。

易错点

权值可以全部为负，最大值单位元必须是LLONG_MIN，不能是0。CHANGE是改成t，并非增加t。路径包含两个端点；同点查询只统计该点。q可以为0，此时不输出任何查询结果。剖分和父亲遍历均采用迭代实现处理最长链。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct HLD {
    int n, tim = 0;
    vector<vector<int>> g;
    vector<int> p, d, sz, heavy, top, id, rev, order;
    HLD(int n)
        : n(n), g(n + 1), p(n + 1), d(n + 1), sz(n + 1, 1), heavy(n + 1), top(n + 1), id(n + 1),
          rev(n + 1) {
        sz[0] = 0;
    }
    void add(int a, int b) {
        g[a].push_back(b);
        g[b].push_back(a);
    }
    void build() {
        order.push_back(1);
        for (int i = 0; i < (int)order.size(); ++i) {
            int u = order[i];
            for (int v : g[u])
                if (v != p[u])
                    p[v] = u, d[v] = d[u] + 1, order.push_back(v);
        }
        for (int i = n - 1; i > 0; --i) {
            int u = order[i], v = p[u];
            sz[v] += sz[u];
            if (sz[u] > sz[heavy[v]])
                heavy[v] = u;
        }
        vector<pair<int, int>> st(1, {1, 1});
        while (!st.empty()) {
            auto q = st.back();
            st.pop_back();
            for (int u = q.first; u; u = heavy[u]) {
                top[u] = q.second;
                id[u] = ++tim;
                rev[tim] = u;
                for (int v : g[u])
                    if (p[v] == u && v != heavy[u])
                        st.push_back({v, v});
            }
        }
    }
};
struct Seg {
    int n;
    vector<ll> s, mx;
    Seg(vector<ll> &a) : n(a.size() - 1), s(4 * n + 4), mx(4 * n + 4) {
        build(1, 1, n, a);
    }
    void pull(int k) {
        s[k] = s[k * 2] + s[k * 2 + 1];
        mx[k] = max(mx[k * 2], mx[k * 2 + 1]);
    }
    void build(int k, int l, int r, vector<ll> &a) {
        if (l == r) {
            s[k] = mx[k] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(k * 2, l, m, a);
        build(k * 2 + 1, m + 1, r, a);
        pull(k);
    }
    void setval(int k, int l, int r, int x, ll v) {
        if (l == r) {
            s[k] = mx[k] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x <= m)
            setval(k * 2, l, m, x, v);
        else
            setval(k * 2 + 1, m + 1, r, x, v);
        pull(k);
    }
    pair<ll, ll> get(int k, int l, int r, int a, int b) {
        if (a <= l && r <= b)
            return {s[k], mx[k]};
        int m = (l + r) / 2;
        pair<ll, ll> x = {0, LLONG_MIN};
        if (a <= m)
            x = get(k * 2, l, m, a, b);
        if (b > m) {
            auto y = get(k * 2 + 1, m + 1, r, a, b);
            x.first += y.first;
            x.second = max(x.second, y.second);
        }
        return x;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    HLD h(n);
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        h.add(u, v);
    }
    h.build();
    vector<ll> a(n + 1);
    for (int u = 1; u <= n; ++u)
        cin >> a[h.id[u]];
    Seg st(a);
    int q;
    cin >> q;
    while (q--) {
        string op;
        int u, v;
        cin >> op >> u >> v;
        if (op == "CHANGE") {
            st.setval(1, 1, n, h.id[u], v);
            continue;
        }
        ll sum = 0, mx = LLONG_MIN;
        while (h.top[u] != h.top[v]) {
            if (h.d[h.top[u]] < h.d[h.top[v]])
                swap(u, v);
            auto x = st.get(1, 1, n, h.id[h.top[u]], h.id[u]);
            sum += x.first;
            mx = max(mx, x.second);
            u = h.p[h.top[u]];
        }
        if (h.d[u] > h.d[v])
            swap(u, v);
        auto x = st.get(1, 1, n, h.id[u], h.id[v]);
        sum += x.first;
        mx = max(mx, x.second);
        cout << (op == "QSUM" ? sum : mx) << '\n';
    }
}