SPOJ - QTREE

#include <bits/stdc++.h>

using namespace std;

// Segment Tree
struct Node {
    int mx;
    Node * left, * right;
    void resetVal() {
        if (left && right) mx = max(left->mx, right->mx);
        else if (right) mx = right->mx;
        else if (left) mx = left->mx;
        else mx = 0;
    }
    void update(int l, int r, int index, int value) {
        if (l+1 == r) {
            mx = value;
            return;
        }
        int mid = (l + r) / 2;
        if (index < mid) {
            if (!left) left = new Node();
            left->update(l, mid, index, value);
        } else {
            if (!right) right = new Node();
            right->update(mid, r, index, value);
        }
        resetVal();
    }
    int rangeMax(int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql) return 0;
        if (ql <= l && r <= qr) return mx;
        int mid = (l + r) / 2;
        int L = (left ? left->rangeMax(l, mid, ql, qr) : 0);
        int R = (right ? right->rangeMax(mid, r, ql, qr) : 0);
        return max(L, R);
    }
};

struct HLD {
    int n;
    vector<int> parent, depth, heavyChild, chainHead, pos;
    int subtree(int v, const vector<vector<int>> &g) {
        int totalSubtree = 1, maxSubtreeSize = 0;
        for (int c : g[v]) {
            if (c != parent[v]) {
                parent[c] = v, depth[c] = depth[v]+1;
                int childSubtree = subtree(c, g);
                totalSubtree += childSubtree;
                if (childSubtree > maxSubtreeSize) {
                    maxSubtreeSize = childSubtree;
                    heavyChild[v] = c;
                }
            }
        }
        return totalSubtree;
    }
    void decompose(int r, const vector<vector<int>> &g) {
        int nextPos = 0;
        function<void(int, int)> recur = [&](int v, int h) {
            chainHead[v] = h, pos[v] = nextPos++;
            if (heavyChild[v] != -1) recur(heavyChild[v], h);
            for (int c : g[v]) {
                if (c != parent[v] && c != heavyChild[v]) recur(c, c);
            }
        };
        recur(r, r);
    }

    // Segment Tree on max edge to parent in range
    Node * root;

    void build(const vector<vector<int>> g) {
        n = g.size();
        parent = depth = chainHead = pos = vector<int>(n);
        heavyChild.assign(n, -1);

        subtree(0, g);
        decompose(0, g);

        root = new Node();
    }
    void updateEdge(int a, int b, int w) { // updates edge from a to b to have weight w
        if (parent[a] == b) swap(a, b);
        root->update(0, n, pos[b], w);
    }
    int maxEdge(int a, int b) { // on path from a to b
        int maxEdge = 0;
        for (; chainHead[a] != chainHead[b]; b = parent[chainHead[b]]) {
            if (depth[chainHead[a]] > depth[chainHead[b]]) swap(a, b);
            maxEdge = max(maxEdge, root->rangeMax(0, n, pos[chainHead[b]], pos[b]+1)); // including both head and b
        }
        if (depth[a] > depth[b]) swap(a, b);
        maxEdge = max(maxEdge, root->rangeMax(0, n, pos[a]+1, pos[b]+1)); // excluding a because it's edge to parent is not on the path
        return maxEdge;
    }
};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> a(n-1), b(n-1), c(n-1); // edge from a to b has cost c
        vector<vector<int>> g(n);
        for (int i = 0; i < n-1; ++i) {
            cin >> a[i] >> b[i] >> c[i];
            --a[i], --b[i];
            g[a[i]].push_back(b[i]);
            g[b[i]].push_back(a[i]);
        }

        HLD d;
        d.build(g);
        for (int i = 0; i < n-1; ++i) d.updateEdge(a[i], b[i], c[i]);
        string s;
        while (cin >> s && s != "DONE") {
            int x, y; cin >> x >> y;
            if (s == "CHANGE") d.updateEdge(a[x-1], b[x-1], y);
            else cout << d.maxEdge(x-1, y-1) << '\n';
        }
    }
    return 0;
}