heavy-light decomposition

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <stdio.h>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <iterator>
#include <map>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <random>
#include <ctime>
#include <chrono>
#include <cstdlib>
#define let int
#define int long long
#define pb push_back
#define fir first
#define sec second
#define double long double
#define endl '\n'
#define un unsigned
#define INF 1000000000000009
#define EPS 0.0000000001
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 1000009, R = 1 << 20, MOD = 1e9 + 7, ABC = 26;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

class SegmentTree {
public:
    vector<int> tree;
    void init(int n) {
        tree.resize(4 * n + 1, 0);
    }

    int findMax(int ql, int qr, int v, int nl, int nr) {
        if (ql > nr || qr < nl)
            return 0;
        if (ql <= nl && qr >= nr)
            return tree[v];
        int nm = (nl + nr) / 2;
        return max(findMax(ql, qr, 2 * v, nl, nm), findMax(ql, qr, v * 2 + 1, nm + 1, nr));
    }

    void upd(int v, int nl, int nr, int pos, int add) {
        if (nl == nr) {
            tree[v] += add;
            return;
        }

        if (v * 2 >= tree.size())
            return;

        int nm = (nl + nr) / 2;
        if (pos <= nm)
            upd(2 * v, nl, nm, pos, add);
        else
            upd(2 * v + 1, nm + 1, nr, pos, add);
        tree[v] = max(tree[v * 2 + 1], tree[v * 2]);
    }
};

class HeavyLightDecomposition {
private:
    vector<vector<int>> gr_;
    vector<int> sz_;
    SegmentTree tree;
    vector<int> pathNumber_;
    vector<int> timeIn_, timeOut_;
    vector<int> parent_;

    int current = 0;
    void dfsBuildPaths(int v, int pr, int path) {
        timeIn_[v] = current++;
        pathNumber_[v] = path;
        for (int i = 0; i < gr_[v].size(); i++) {
            int nv = gr_[v][i];
            if (nv != pr) {
                if (sz_[nv] * 2 >= sz_[v]) {
                    //swap(gr_[v][i], gr_[v][0]);
                    dfsBuildPaths(nv, v, path);
                }
                else {
                    dfsBuildPaths(nv, v, nv);
                }
            }
        }
        timeOut_[v] = current;
    }

    void dfs(int v, int pr) {
        for (int i = 0; i < gr_[v].size(); i++) {
            int nv = gr_[v][i];
            if (nv != pr) {
                if (sz_[nv] * 2 >= sz_[v]) {
                    swap(gr_[v][i], gr_[v][0]);
                    dfs(nv, v);
                }
                else {
                    dfs(nv, v);
                }
            }
        }
    }
    void dfsFindSz(int v, int parent) {
        sz_[v] = 1;
        parent_[v] = parent;
        for (int u : gr_[v]) {
            if (parent != u) {
                dfsFindSz(u, v);
                sz_[v] += sz_[u];
            }
        }
    }

    bool isAncestor(int u, int v) {
        return timeIn_[u] <= timeIn_[v] && timeOut_[v] <= timeOut_[u];
    }

public:
    HeavyLightDecomposition(const vector<vector<int>>& gr) : gr_(gr) {}

    void init() {
        int n = gr_.size();
        sz_.assign(n, 0);
        tree.init(n);
        timeIn_.assign(n, 0);
        timeOut_.assign(n, 0);
        parent_.assign(n, -1);
        pathNumber_.assign(n, -1);
        dfsFindSz(0, -1);
        dfs(0, -1);
        dfsBuildPaths(0, -1, 0);
    }

    int findMax(int u, int v) {
        int ans = -INF;

        while (!isAncestor(pathNumber_[u], v)) {
            int path = pathNumber_[u];
            ans = max(ans, tree.findMax(timeIn_[path], timeIn_[u], 1, 0, tree.tree.size() / 4 - 1));
            u = parent_[path];
        }

        while (!isAncestor(pathNumber_[v], u)) {
            int path = pathNumber_[v];
            ans = max(ans, tree.findMax(timeIn_[path], timeIn_[v], 1, 0, tree.tree.size() / 4 - 1));
            v = parent_[path];
        }

        if (timeIn_[u] > timeIn_[v])
            swap(u, v);

        ans = max(ans, tree.findMax(timeIn_[u], timeIn_[v], 1, 0, tree.tree.size() / 4 - 1));
        return ans;
    }

    void update(int pos, int x) {
        tree.upd(1, 0, tree.tree.size() / 4 - 1 , timeIn_[pos], x);
    }
};

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));

    int n;
    cin >> n;

    vector<vector<int>> gr(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }

    int q;
    cin >> q;

    HeavyLightDecomposition hld(gr);
    hld.init();

    while (q--) {
        char c;
        int u, v;
        cin >> c >> u >> v;

        if (c == 'I') {
            hld.update(u - 1, v);
        }
        else {
            int ans = hld.findMax(u - 1, v - 1);
            cout << ans << endl;
        }
    }
}