SPOJ QTREE LCT

#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) qqbx(#a, a)
#define pary(a...) danb(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\033[1;32m[ " << s << " ] = [ ";
    for (auto it = L; it != R; ++it)
        std::cerr << *it << ' ';
    std::cerr << "]\033[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define pb emplace_back
#define sort_uni(v) sort(all(v)),v.erase(unique(all(v)), v.end())
#define get_pos(u,v) int(lower_bound(all(u), v) - u.begin())

using namespace std;
using ll = int64_t;
using ld = long double;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
const int maxn = 100025;

struct LinkCutTree {
    struct node {
        int pa, ch[2];
        int val, mx;
        node() : pa(), ch{}, val(), mx() {}
        node(int p, int c) : pa(p), ch{}, val(c), mx(c) {}
    } S[maxn];
    void init(int n) {
        for (int i = 1; i <= n; i++) S[i] = node();
    }
    void pull(int x) {
        S[x].mx = max({ S[x].val, S[S[x].ch[0]].mx, S[S[x].ch[1]].mx });
    }
    bool dir(int x) {
        return S[S[x].pa].ch[1] == x;
    }
    bool isRoot(int x) {
        return S[S[x].pa].ch[dir(x)] != x;
    }
    void rot(int x) {
        int y = S[x].pa, z = S[y].pa, d = dir(x);
        S[x].pa = z;
        if (!isRoot(y)) S[z].ch[dir(y)] = x;
        S[y].ch[d] = S[x].ch[!d];
        if (S[x].ch[!d]) S[S[x].ch[!d]].pa = y;
        S[y].pa = x;
        S[x].ch[!d] = y;
        pull(x);
        pull(y);
    }
    void splay(int x) {
        while (!isRoot(x)) {
            if (int y = S[x].pa; !isRoot(y))
                rot(dir(x) != dir(y) ? y : x);
            rot(x);
        }
    }
    int access(int x) {
        int last = 0;
        while (x) {
            splay(x);
            S[x].ch[1] = last;
            pull(x);
            last = x;
            x = S[x].pa;
        }
        return last;
    }
    int query(int a, int b) {
        access(a);
        int lca = access(b);
        if (lca != a) {
            splay(a);
            return max(S[S[lca].ch[1]].mx, S[a].mx);
        } else {
            return S[S[lca].ch[1]].mx;
        }
    }
    void modify(int i, int v) {
        splay(i);
        S[i].val = v;
        pull(i);
    }
} lct;

vector<tuple<int,int,int>> g[maxn];
int below[maxn];
void dfs(int i, int p) {
    for (auto [j, c, id]: g[i]) {
        if (j == p) continue;
        below[id] = j;
        lct.S[j] = LinkCutTree::node(i, c);
        dfs(j, i);
    }
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) g[i].clear();
        lct.init(n);
        for (int i = 1; i < n; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            g[a].pb(b, c, i);
            g[b].pb(a, c, i);
        }
        dfs(1, 0);
        string com;
        while (cin >> com && com != "DONE") {
            if (com == "CHANGE") {
                int a, b;
                cin >> a >> b;
                lct.modify(below[a], b);
            } else if (com == "QUERY") {
                int a, b;
                cin >> a >> b;
                cout << lct.query(a, b) << '\n';
            }
        }
    }
}