树剖求调，AC on 1

Code

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100005;
struct egde{
    int a, b, c;
}e[N];
struct Edge{
    int e, to, nxt;
}g[N << 1];
int h[N], idx;
int dfn[N], vis_cnt;
int big_son[N], siz[N], top[N], dep[N], father[N];
int w[N << 2], num[N], n;
void add(int a,int b,int c)
{
    g[++idx] = {c, b, h[a]}, h[a] = idx;
}
inline void pushup(int u)
{
    w[u] = max(w[u * 2], w[u * 2 + 1]);
}
void dfs1(int u,int fa)
{
    father[u] = fa;
    dfn[u] = ++vis_cnt;
    siz[u] = 1;
    for (int i = h[u]; i; i = g[i].nxt)
    {
        int j = g[i].to;
        if (j == fa)
            continue;
        dep[j] = dep[u] + 1;
        dfs1(j, u);
        siz[u] += siz[j];
        if (siz[j] > siz[big_son[u]])
            big_son[u] = j;
        num[dfn[j]] = g[i].e;
    }
}
void dfs2(int u,int fa,int Top)
{
    top[u] = Top;
    if (big_son[u])
        dfs2(big_son[u], u, Top);
    for (int i = h[u]; i; i = g[i].nxt)
    {
        int j = g[i].to;
        if (j == fa || j == big_son[u])
            continue;
        dfs2(j, u, j);
    }
}
void build(int u,int l,int r)
{
    if (l == r)
    {
        w[u] = num[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);
    pushup(u);
}
void update(int u,int l,int r,int x,int v)
{
    if (l == r)
    {
        w[u] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
        update(u * 2, l, mid, x, v);
    else
        update(u * 2 + 1, mid + 1, r, x, v);
    pushup(u);
}
int query1(int u,int l,int r,int L,int R)
{
    if (L <= l && r <= R)
        return w[u];
    if (r < L || R < l)
        return 0;
    int mid = (l + r) >> 1;
    return max(query1(u * 2, l, mid, L, R), query1(u * 2 + 1, mid + 1, r, L, R));
}
int query2(int x,int y)
{
    int ans = 0;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        ans = max(ans, query1(1, 1, n, dfn[top[x]], dfn[x]));
        x = father[top[x]];
    }
    if (x != y)
        ans = max(ans, query1(1, 1, n, min(dfn[x], dfn[y]) + 1, max(dfn[x], dfn[y])));
    return ans;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int a, b, c;
        scanf("%d%d%d",&a,&b,&c);
        add(a, b, c);
        add(b, a, c);
        e[i] = {a, b, c};
    }   
    dfs1(1, 1);
    dfs2(1, 1, 1);
    build(1, 1, n);
    for (;;)
    {
        char op[10];
        scanf("%s", op);
        if (op[0] == 'D')
            return 0;
        int x, y;
        scanf("%d%d",&x,&y);
        if (op[0] == 'C')
        {
            int a = e[x].a, b = e[x].b;
            if (father[b] == a)
                a = b;
            update(1, 1, n, dfn[a], y);
        }
        else
            printf("%d\n", query2(x, y));
    }
    return 0;
}