Why CE

rt

# include <bits/stdc++.h>
//# include <windows.h>
# define I return

# define AK 0

# define IOI ;

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

struct node {

    int x, w, id;

} ;

int n, s[100005], heavist[100005], x, y, tot, dfn[100005], a[100005], tr[400005], k, st[100005], depth[100005], f[100005], mp[100005];

string op;

vector <node> v[100005];

void init1 (const int x, const int fa) {

    s[x] = 1, f[x] = fa;

    depth[x] = depth[fa] + 1;

    for (const node& i : v[x])
        if (i.x != fa) {

            mp[i.id] = i.x;

            init1 (i.x, x);

            s[x] += s[i.x];

            if (s[heavist[x]] < s[i.x])
                heavist[x] = i.x;

        }

    return ;

}

void init2 (const int x, const int fa, const int s) {

    dfn[x] = ++ tot, st[x] = s;
//  cerr << x << ':' << dfn[x] << ',' << st[x] << ',' << depth[x] << ',' << ::s[x] << ',' << heavist[x] << '\n';
    if (! heavist[x])
        return ;

    init2 (heavist[x], x, s);

    for (const node& i : v[x])
        if (i.x != fa && i.x != heavist[x])
            a[i.x] = i.w, init2 (i.x, x, i.x);

    return ;

}

void build (const int x, const int l, const int r) {

    if (l == r) {

        tr[x] = a[l];

        return ;

    }

    const int mid = l + r >> 1, left = x << 1, right = left | 1;

    build (left, l, mid), build (right, mid + 1, r);

    tr[x] = max (tr[left], tr[right]);

    return ;

}

void change (const int x, const int l, const int r, const int t) {

    if (l == t) {

        tr[x] = max (tr[x], k);

        return ;

    }

    const int mid = l + r >> 1, left = x << 1, right = left | 1;

    if (t <= mid)
        change (left, l, mid, t);
    else
        change (right, mid + 1, r, t);

    tr[x] = max (tr[left], tr[right]);

    return ;

}

int find (const int x, const int l, const int r, const int L, const int R) {

    if (l == L && r == R)
        return tr[x];

    const int mid = l + r >> 1, left = x << 1, right = left | 1;

    if (R <= mid)
        return find (left, l, mid, L, R);

    if (L > mid)
        return find (right, mid + 1, r, L, R);

    return max (find (left, l, mid, L, mid), find (right, mid + 1, r, mid + 1, R));

}

int find_path (int x, int y) {

    int maxx = 0;

    while (st[x] != st[y]) {

        if (depth[st[x]] < depth[st[y]])
            swap (x, y);

        maxx = max (maxx, find (1, 1, n, dfn[st[x]], dfn[x]));
//      cerr << st[x] << '~' << x << ':' << sum << '\n';
        x = f[st[x]];

    }

    if (dfn[x] > dfn[y])
        swap (x, y);

    if (dfn[x] < dfn[y])
        maxx = max (maxx, find (1, 1, n, dfn[x] + 1, dfn[y]));

    return maxx;

}

void change_edge (const int x) {

    change (1, 1, n, dfn[x]);

    return ;

}

int main () {

    ios::sync_with_stdio (0);

    cin.tie (0);

    cout.tie (0);

    cin >> n;

    for (int i = 1; i < n; ++ i)
        cin >> x >> y >> k, v[x].emplace_back (y, k, i), v[y].emplace_back (x, k, i);

    init1 (1, 0), init2 (1, 0, 1);

    while (cin >> op, op[0] != 'D') {

        cin >> x >> y;

        if (op[0] == 'C')
            k = y, change_edge (x);
        else
            cout << find_path (x, y) << '\n';
//      # include <windows.h>
//      Sleep (1000);
//      system ("pause");
    }

    I AK IOI

}