树剖 WA 0 pts 求调

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 10;
int n, a[N];
int fa[N], dep[N], sz[N], son[N];
int clk, top[N], dfn[N];
int id, head[N << 1], to[N << 1], nxt[N << 1];
ll w[N << 1], val[N << 2];
struct edge{
    int u, v;
    ll w;
} e[N];

void add(int u, int v, ll ww){
    to[++id] = v, w[id] = ww;
    nxt[id] = head[u], head[u] = id;
}

void dfs(int u, int father){
    sz[u] = 1;
    for(int i=head[u];i;i=nxt[i]){
        int v = to[i];
        if(v == father)
            continue;
        dep[v] = dep[u] + 1, fa[v] = u;
        a[v] = e[i].w;
        dfs(v, u);
        sz[u] += sz[v];
        if(!son[u] || sz[v] > sz[son[u]])
            son[u] = v;
    }
}

void build(int u, int t){
    dfn[u] = ++clk;
    top[u] = t;
    if(son[u])
        build(son[u], t);
    for(int i=head[u];i;i=nxt[i]){
        int v = to[i];
        if(v == fa[u])
            continue;
        if(v != son[u])
            build(v, v);
    }
}

#define ls(o) (o << 1)
#define rs(o) (o << 1 | 1)

void update(int o, int l, int r, int p, ll x){
    if(l == r){
        val[o] = x;
        return ;
    }
    int mid = (l + r) >> 1;
    if(p <= mid)
        update(ls(o), l, mid, p, x);
    else
        update(rs(o), mid + 1, r, p, x);
    val[o] = max(val[ls(o)], val[rs(o)]);
}

ll query(int o, int l, int r, int s, int t){
    if(l >= s && r <= t)
        return val[o];
    int mid = (l + r) >> 1;
    ll res = -1e18;
    if(s <= mid)
        res = max(res, query(ls(o), l, mid, s, t));
    if(t > mid)
        res = max(res, query(rs(o), mid + 1, r, s, t));
    return res;
}

ll query_ans(int u, int v){
    if(u == v)
        return 0;
    ll res = -1e18;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]])
            swap(u, v);
        res = max(res, query(1, 1, n, dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if(dep[u] > dep[v])
        swap(u, v);
    res = max(res, query(1, 1, n, dfn[u] + 1, dfn[v]));//注意维护的是边权 
    return res;
}

int main(){
    scanf("%d", &n);
    for(int i=1,u,v;i<n;i++){
        ll ww;
        scanf("%d%d%lld", &u, &v, &ww);
        add(u, v, ww), add(v, u, ww);
        e[i] = (edge){u, v, ww};
    }
    dfs(1, 0);
    build(1, 1);
    for(int u=1;u<=n;u++)
        update(1, 1, n, dfn[u], a[u]);
    char op[20];
    while(~scanf("%s", op)){
        int a, b;
        ll ww;
        if(op[0] == 'D')
            break;
        if(op[0] == 'C'){
            scanf("%d%lld", &a, &ww);
            if(dep[e[a].u] > dep[e[a].v])
                b = e[a].u;
            else
                b = e[a].v;
            update(1, 1, n, dfn[b], ww);
        }
        else{
            scanf("%d%d", &a, &b);
            printf("%lld\n", query_ans(a, b));
        }
    }
    return 0;
}