树剖全RE求调

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 4e6+5;
namespace data_structures{
//#define ll long long 
#define ull unsigned long long
#define lid (id << 1)
#define rid (id << 1 | 1)
    struct Seg_node{
        int l, r;
        ll sum, mn, mx;
        ll lazy;
    };
    struct segment_tree{
        int n;
        int a[N];
        Seg_node tr[N << 2];
        void clear(){
            memset(a, 0, sizeof(a));
        }
        void pushup(int id){
            tr[id].sum = tr[lid].sum + tr[rid].sum;
            tr[id].mn = min(tr[lid].mn, tr[rid].mn);
            tr[id].mx = max(tr[lid].mx, tr[rid].mx);
        }
        void pushdown(int id){
            if (tr[id].lazy){
                tr[lid].lazy += tr[id].lazy;
                tr[rid].lazy += tr[id].lazy;
                tr[lid].mn += tr[id].lazy;
                tr[rid].mn += tr[id].lazy;
                tr[lid].mx += tr[id].lazy;
                tr[rid].mx += tr[id].lazy;
                tr[lid].sum += tr[id].lazy * (tr[lid].r - tr[lid].l + 1);
                tr[rid].sum += tr[id].lazy * (tr[rid].r - tr[rid].l + 1);
                tr[id].lazy = 0;
            }
        }
        void build(int id, int l, int r){
            tr[id].l = l;
            tr[id].r = r;
            tr[id].lazy = 0;
            if (l >= r){
                tr[id].mx = a[l];
                tr[id].mn = a[l];
                tr[id].sum = a[l];
                return;
            }
            int mid = (tr[id].l + tr[id].r) / 2;
            build(lid, l, mid);
            build(rid, mid + 1, r);
            pushup(id);
        }   
        void add(int id, int l, int r, ll val){
            if (l <= tr[id].l && tr[id].r <= r){
                tr[id].sum += val * (tr[id].r - tr[id].l + 1);
                tr[id].mx += val;
                tr[id].mn += val;
                tr[id].lazy += val;
                return;
            }
            pushdown(id);
            int mid = (tr[id].l + tr[id].r) >> 1;
            if (r <= mid) add(lid, l, r, val);
            else if (l > mid) add(rid, l, r, val);
            else add(lid, l, mid, val), add(rid, mid + 1, r, val);
            pushup(id);
        }
        void modify(int id, int x, ll y){
            if (tr[id].l == tr[id].r){
                tr[id].sum = tr[id].mx = tr[id].mx = y;
                return;
            }
            int mid = (tr[id].l + tr[id].r) >> 1;
            if (x <= mid) modify(lid, x, y);
            else modify(rid, x, y);
            pushup(id);
        }
        ll query_sum(int id, int l, int r){
            if (l <= tr[id].l && tr[id].r <= r) return tr[id].sum;
            pushdown(id);
            int mid = (tr[id].l + tr[id].r) >> 1;
            if (r <= mid) return query_sum(lid, l, r);
            if (l > mid) return query_sum(rid, l, r);
            return query_sum(lid, l, mid) + query_sum(rid, mid + 1, r);
        }
        ll query_max(int id, int l, int r){
            if (l <= tr[id].l && tr[id].r <= r) return tr[id].mx;
            pushdown(id);
            int mid = (tr[id].l + tr[id].r) >> 1;
            if (r <= mid) return query_max(lid, l, r);
            if (l > mid) return query_max(rid, l, r);
            return max(query_max(lid, l, mid), query_max(rid, mid + 1, r));
        }
        ll query_min(int id, int l, int r){
            if (l <= tr[id].l && tr[id].r <= r) return tr[id].mn;
            pushdown(id);
            int mid = (tr[id].l + tr[id].r) >> 1;
            if (r <= mid) return query_min(lid, l, r);
            if (l > mid) return query_min(rid, l, r);
            return min(query_min(lid, l, mid), query_min(rid, mid + 1, r));
        }
        void print(int n){
            cout << "segtree:";
            for (int i = 1;i <= n;i++){
                cout << query_sum(1, i, i) << ' ';
            }
            cout << '\n';
        }
    };
}
using namespace data_structures;
ll n, q;
ll head[N], nxt[N], to[N], val[N], cccnnnttt, u[N], v[N], w[N], val1[N];
ll fa[N], dep[N], siz[N], hson[N], top[N], dfn[N], rnk[N], cnt;
ll a[N];
segment_tree sgt;
void add1(ll u, ll v, ll w){
    to[++cccnnnttt] = v;
    nxt[cccnnnttt] = head[u];
    val1[cccnnnttt] = w;
    head[u] = cccnnnttt;
}
void dfs1(ll u, ll f){
    hson[u] = -1;
    siz[u] = 1;
    ll maxson = -1;
    for (ll i = head[u];i;i = nxt[i]){
        ll v = to[i];
        if (v != f){
            dep[v] = dep[u] + 1;
            fa[v] = u;
            val[v] = val1[i];
            dfs1(v, u);
            siz[u] += siz[v];
            if (siz[v] > maxson) maxson = siz[v], hson[u] = v;
        }
    }
}
void dfs2(ll u, ll t){
    top[u] = t;
    dfn[u] = ++cnt;
    rnk[cnt] = u;
    sgt.a[dfn[u]] = val[u];
    if (hson[u] == -1) return;
    dfs2(hson[u], t);
    for (ll i = head[u];i;i = nxt[i]){
        ll v = to[i];
        if (v != hson[u] && v != fa[u]) dfs2(v, v);
    }
}
ll qrangesum(int x, int y){
    ll ans = 0;
    while (top[x] != top[y]){
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += sgt.query_sum(1, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    ans += sgt.query_sum(1, dfn[x], dfn[y]);
    return ans;
}
ll qrangemax(int x, int y){
    ll ans = LONG_LONG_MIN;
    while (top[x] != top[y]){
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans = max(ans, sgt.query_max(1, dfn[top[x]], dfn[x]));
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    ans = max(ans, sgt.query_max(1, dfn[x] + 1, dfn[y]));
    return ans;
}
void addrange(int x, int y, ll k){
    while (top[x] != top[y]){
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        sgt.add(1, dfn[top[x]], dfn[x], k);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    sgt.add(1, dfn[x], dfn[y], k);
}
ll qsubtreesum(int x){
    return sgt.query_sum(1, dfn[x], dfn[x] + siz[x] - 1);
}
ll qsubtreemax(int x){
    return sgt.query_max(1, dfn[x], dfn[x] + siz[x] - 1);
}
void addsubtree(int x, ll k){
    sgt.add(1, dfn[x], dfn[x] + siz[x] - 1, k);
}
ll qnode(int x){
    return sgt.query_sum(1, dfn[x], dfn[x]);
}
void modifynode(int x, ll k){
    sgt.modify(1, dfn[x], k);
}
int main(){
    cin >> n;
    for (int i = 1;i < n;i++){
        cin >> u[i] >> v[i] >> w[i];
        add1(u[i], v[i], w[i]);
        add1(v[i], u[i], w[i]);
    }
    val[1] = 0;
    dep[1] = 1;
    dfs1(1, 0);
    dfs2(1, 1);
    sgt.build(1, 1, n);
    while (1){
        string s;
        int a, b;
        cin >> s;
        if (s == "DONE") break;
        cin >> a >> b;
        if (s == "CHANGE"){
            modifynode(v[a], b);
        }
        else{
            cout << qrangemax(a, b) << '\n';
        }
    }
    return 0;
}