树剖 20pts 求助

#include <cstdio>
#include <vector>
using namespace std;
const int N = 100005;
vector < int > to[N];
int size[N], son[N], dep[N], fa[N];
void dfs1(int u, int father) {
    size[u] = 1;
    dep[u] = dep[father] + 1;
    fa[u] = father;
    for (int v : to[u]) {
        if (v != father) {
            dfs1(v, u);
            size[u] += size[v];
            if (size[v] > size[son[u]]) {
                son[u] = v;
            }
        }
    }
}
int top[N], dfn[N], dfncnt, a[N], b[N];
void dfs2(int u, int toplink) {
    top[u] = toplink;
    dfncnt++;
    dfn[u] = dfncnt;
    b[dfn[u]] = a[u];
    if (son[u] != 0) {
        dfs2(son[u], toplink);
        for (int v : to[u]) {
            if (v != son[u] && v != fa[u]) {
                dfs2(v, v);
            }
        }
    }
}
int max(int a, int b) {
    return a > b ? a : b;
}
struct Edge {
    int l, r, w;
} node[4 * N];
void push_up(int p) {
    node[p].w = max(node[2 * p].w, node[2 * p + 1].w);
}
void build(int p, int l, int r) {
    node[p].l = l;
    node[p].r = r;
    if (l == r) {
        node[p].w = b[l];
    } else {
        int mid = (l + r) / 2;
        build(2 * p, l, mid);
        build(2 * p + 1, mid + 1, r);
        push_up(p);
    }
}
void modify(int p, int pos, int value) {
    if (node[p].l == node[p].r) {
        node[p].w = value;
    } else {
        int mid = (node[p].l + node[p].r) / 2;
        if (pos <= mid) {
            modify(2 * p, pos, value);
        } else {
            modify(2 * p + 1, pos, value);
        }
        push_up(p);
    }
}
int query(int p, int l, int r) {
    if (l <= node[p].l && node[p].r <= r) {
        return node[p].w;
    } else {
        int ans = 0;
        int mid = (node[p].l + node[p].r) / 2;
        if (l <= mid) {
            ans = max(ans, query(2 * p, l, r));
        }
        if (mid + 1 <= r) {
            ans = max(ans, query(2 * p + 1, l, r));
        }
        return ans;
    }
}
int query(int u, int v) {
    int ans = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) {
            u ^= v ^= u ^= v;
        }
        ans = max(ans, query(1, dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) {
        u ^= v ^= u ^= v;
    }
    ans = max(ans, query(1, dfn[u], dfn[v]));
    return ans;
}
int edge_u[N], edge_v[N], edge_w[N];
char op[7];
int main() {
    int n;
    scanf("%d", &n);
    for (int u = 1; u <= n; u++) {
        to[u].clear();
    }
    for (int i = 1; i < n; i++) {
        scanf("%d %d %d", &edge_u[i], &edge_v[i], &edge_w[i]);
        to[edge_u[i]].push_back(edge_v[i]);
        to[edge_v[i]].push_back(edge_u[i]);
    }
    dfs1(1, 0);
    for (int i = 1; i < n; i++) {
        if (fa[edge_u[i]] == edge_v[i]) {
            a[edge_u[i]] = edge_w[i];
        } else {
            a[edge_v[i]] = edge_w[i];
        }
    }
    dfs2(1, 1);
    build(1, 1, n);
    while (true) {
        scanf("%s", op);
        if (op[0] == 'Q') {
            int u, v;
            scanf("%d %d", &u, &v);
            printf("%d\n", query(u, v));
        } else if (op[0] == 'C') {
            int i, t;
            scanf("%d %d", &i, &t);
            if (fa[edge_u[i]] == edge_v[i]) {
                modify(1, dfn[edge_u[i]], t);
            } else {
                modify(1, dfn[edge_v[i]], t);
            }
        } else {
            break;
        }
    }
    return 0;
}