萌新初学熟练剖粪，30pts求条(AC#4#5#8))

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,tot,a[200005],dep[200005],up[200005],sz[200005],in[200005],fa[200005];//a初始权值，dep深度，up链顶，sz子树大小，in dfs序，fa父亲
vector<int> g[200005];//树
struct Segment_tree{
    struct node{int l,r,maxn,sum;}a[800005];
    void build(int op,int l,int r){
    	a[op].l = l;
    	a[op].r = r;
    	if (l == r) return;
    	int mid = (l + r) / 2;
    	build(op * 2,l,mid);
    	build(op * 2 + 1,mid + 1,r);
    }
    void change(int op,int p,int x){
        if (a[op].l == a[op].r){
            a[op].sum = a[op].maxn = x;
            return;
        }
    	int mid = (a[op].l + a[op].r) / 2;
    	if (a[op].l <= p && p <= mid) change(op * 2,p,x);
    	else change(op * 2 + 1,p,x);
    	a[op].sum = a[op * 2].sum + a[op * 2 + 1].sum;
    	a[op].maxn = max(a[op * 2].maxn,a[op * 2 + 1].maxn);
    }
    int query_sum(int op,int l,int r){
    	if (l <= a[op].l && a[op].r <= r) return a[op].sum;
    	int mid = (a[op].l + a[op].r) / 2,ans = 0;
    	if (l <= mid && a[op].l <= r) ans += query_sum(op * 2,l,r);
    	if (l <= a[op].r && mid < r) ans += query_sum(op * 2 + 1,l,r);
    	return ans;
    }
    int query_max(int op,int l,int r){
    	if (l <= a[op].l && a[op].r <= r) return a[op].maxn;
    	int mid = (a[op].l + a[op].r) / 2,ans = INT_MIN;
    	if (l <= mid && a[op].l <= r) ans = max(ans,query_max(op * 2,l,r));
    	if (l <= a[op].r && mid < r) ans = max(ans,query_max(op * 2 + 1,l,r));
    	return ans;
    }
}tree;
void dfs1(int x,int f){
    dep[x] = dep[f] + 1;
    sz[x] = 1;
    fa[x] = f;
    for (int i = 0; i < g[x].size(); i++){
        int nxt = g[x][i];
        if (nxt != f){
            dfs1(nxt,x);
            sz[x] += sz[nxt];
        }
    }
}
void dfs2(int x,int u){
    up[x] = u;
    in[x] = ++tot;
    tree.change(1,tot,a[x]);
    sort(g[x].begin(),g[x].end(),[](int x,int y){return sz[x] > sz[y];});
    for (int i = 0; i < g[x].size(); i++){
        int nxt = g[x][i];
        if (nxt != fa[x]) dfs2(nxt,i == (x != 1) ? u : nxt);
    }
}
int ask_max(int x,int y){
    int res = INT_MIN;
    while (up[x] != up[y]){
        if (dep[up[x]] < dep[up[y]]) swap(x,y);
        res = max(res,tree.query_max(1,in[up[x]],in[x]));
        x = fa[up[x]];
    }
    return max(res,tree.query_max(1,min(in[x],in[y]),max(in[x],in[y])));
}
int ask_sum(int x,int y){
    int res = 0;
    while (up[x] != up[y]){
        if (dep[up[x]] < dep[up[y]]) swap(x,y);
        res += tree.query_sum(1,in[up[x]],in[x]);
        x = fa[up[x]];
    }
    return res + tree.query_sum(1,min(in[x],in[y]),max(in[x],in[y]));
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    tree.build(1,1,n);
    for (int i = 1,x,y; i < n; i++){
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) cin >> a[i];
    dfs1(1,0);
    dfs2(1,1);
    for (cin >> m; m--; ){
        string op;
        int x,y;
        cin >> op >> x >> y;
        if (op == "CHANGE") tree.change(1,x,y);
        else if (op == "QMAX") cout << ask_max(x,y) << '\n';
        else cout << ask_sum(x,y) << '\n';
    }
    return 0;
}