rt，好久没打树剖了，样例过，测试全 T

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 5;
int dep[N], size[N], a[N], son[N], f[N], top[N], _, id[N], w[N];
vector<int> g[N];
struct Segment_Tree
{
    struct node
    {
        int l, r, maxn;
    }tr[N << 2];
    void build(int u, int l, int r)
    {
        tr[u].l = l, tr[u].r = r;
        if(l == r) {
            tr[u].maxn = a[l];
            return ;
        }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
    }
    void update(int u, int l, int r, int k)
    {
        if(l <= tr[u].l && tr[u].r <= r)
        {
            tr[u].maxn = k;
            return ;
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) update(u << 1, l, r, k);
        if(r >  mid) update(u << 1 | 1, l, r, k);
        tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
    }
    int query(int u, int l, int r)
    {
        if(l <= tr[u].l && tr[u].r <= r)
        {
            return tr[u].maxn;
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        int res = 0;
        if(l <= mid) res = max(res, query(u << 1, l, r));
        if(r >  mid) res = max(res, query(u << 1 | 1, l, r));
        tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
        return res;
    }
}seg;

struct ShuPou
{
    int query(int x, int y)
    {
        int ans = 0;
        while(top[x] != top[y]){
            if(dep[top[x]] < dep[top[x]]) swap(x, y);
            ans += seg.query(1, id[top[x]], id[x]);
            x = f[top[x]];
        }
        if(dep[x] > dep[y]) swap(x, y);
        ans += seg.query(1, id[x] + 1, id[y]);
        return ans;
    }
}sp;

void dfs1(int u, int fa, int deep)
{
    dep[u] = deep;
    f[u] = fa;
    size[u] = 1;
    int maxn = -1;
    for(int i = 0;i < g[u].size();i ++ ){
        int v = g[u][i];
        if(v == fa) continue;
        dfs1(v, u, deep + 1);
        size[u] += size[v];
        if(size[v] > maxn){
            maxn = size[v];
            son[u] = v;
        }
    }
}

void dfs2(int u, int topfa)
{
    id[u] = ++_;
    a[_] = w[u];
    top[u] = topfa;
    if(!son[u]) return ;
    dfs2(son[u], topfa);
    for(int i = 0;i < g[u].size();i ++ ){
        int v = g[u][i];
        if(v == f[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

int main()
{
    int n; cin >> n;
    for(int i = 1;i < n;i ++ ){
        int u, v, wi; cin >> u >> v >> wi;
        g[u].push_back(v), g[v].push_back(u);
        w[v] = wi;
    }
//    cout << '-';
    dfs1(1, 0, 1), dfs2(1, 1);
    seg.build(1, 1, n);
//    cout << sp.query(1, 3);
    string str; cin >> str;
    while(str != "DONE")
    {
        int a, b; cin >> a >> b;
        if(str == "CHANGE"){
            seg.update(1, id[a] + 1, id[a] + 1, b);
        }
        else cout << sp.query(a, b) << endl;
        
        cin >> str;
    }
    return 0;
}