heavy-light decomposition

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <string>
#include <deque>
#include <iomanip>
#include <cstddef>
#include <queue>


using namespace std;

vector<vector<int> > g, chain;
int num[100100], used[100100], fin[100100], key[100100], unkey[100100], par[100100], val[100100];
int tree[1000100];
vector<vector<long long> > t;
pair<int, int> pos[100100];
vector<int> ord;

void dfsCount(int v)
{
    used[v] = 1;
    ++num[v];

    for (int i = 0; i < g[v].size(); i++) {
        int to = g[v][i];
        if (!used[to])
        {
            dfsCount(to);
            num[v] += num[to];
            par[to] = v;
        }
    }
}

void dfsChain(int v)
{
    used[v] = 1;
    bool f = 1;

    for (int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i];
        if (!used[to])
        {
            dfsChain(to);
            if (2 * num[to] >= num[v])
            {
                pos[v] = make_pair(pos[to].first, chain[pos[to].first].size());
                chain[pos[v].first].push_back(v);
                f = 0;
            }
        }
    }

    if (f)
    {
        pos[v] = make_pair(v, 0);
        chain[v].push_back(v);
    }
}

int timer = 0;

void dfsLca(int v)
{
    used[v] = 1;
    key[v] = timer++;
    unkey[key[v]] = v;
    if (fin[v] == -1)
        fin[v] = ord.size();
    ord.push_back(key[v]);

    for (int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i];
        if (!used[to])
        {
            dfsLca(to);
            ord.push_back(key[v]);
        }
    }
}

int findmin(int v, int l, int r, int lv, int rv)
{
    if (l == lv && r == rv)
        return tree[v];

    int m = (l + r) / 2;
    if (m >= rv)
        return findmin(2 * v + 1, l, m, lv, rv);
    else
        if (m <= lv)
            return findmin(2 * v + 2, m, r, lv, rv);
    return min(findmin(2 * v + 1, l, m, lv, m), findmin(2 * v + 2, m, r, m, rv));
}

void inc(int v, int l, int r, int k)
{
    if (l + 1 == r)
    {
        tree[v] = ord[k];
        return;
    }
    int m = (l + r) / 2;
    if (m > k)
        inc(2 * v + 1, l, m, k);
    else
        inc(2 * v + 2, m, r, k);
    tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
}

void modify(int line, int v, int l, int r, int k)
{
    if (l + 1 == r)
    {
        t[line][v] = val[k];
        return;
    }
    int m = (l + r) / 2;
    if (m > pos[k].second)
        modify(line, 2 * v + 1, l, m, k);
    else
        modify(line, 2 * v + 2, m, r, k);
    t[line][v] = max(t[line][2 * v + 1], t[line][2 * v + 2]);
}

long long findmax(int line, int v, int l, int r, int lv, int rv)
{
    if (l == lv && r == rv)
        return t[line][v];
    int m = (l + r) / 2;
    if (m >= rv)
        return findmax(line, 2 * v + 1, l, m, lv, rv);
    else
        if (m <= lv)
            return findmax(line, 2 * v + 2, m, r, lv, rv);
    return max(findmax(line, 2 * v + 1, l, m, lv, m), findmax(line, 2 * v + 2, m, r, m, rv));
}

long long sum(int a, int b)
{
    long long m = 0;
    while (a != 0 && pos[a].first != pos[b].first)
    {
        int d = chain[pos[a].first].back();
        m = max(m, findmax(pos[a].first, 0, 0, chain[pos[a].first].size(), pos[a].second, chain[pos[a].first].size()));
        a = par[d];
    }
    return max(m, findmax(pos[a].first, 0, 0, chain[pos[a].first].size(), pos[a].second, pos[b].second + 1));
}

int main()
{
    int n, x, y;
    cin >> n;
    g.resize(n);

    for (int i = 0; i < n - 1; i++)
    {
        cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    fill(used, used + n, 0);
    fill(num, num + n, 0);
    par[0] = 0;
    dfsCount(0);

    fill(used, used + n, 0);
    chain.resize(n);
    dfsChain(0);

    fill(used, used + n, 0);
    fill(fin, fin + n, -1);
    dfsLca(0);

    for (int i = 0; i < ord.size(); i++)
        inc(0, 0, ord.size(), i);

    int m;
    char c;
    cin >> m;

    fill(val, val + n, 0);
    t.resize(chain.size());
    for (int i = 0; i < t.size(); i++)
        t[i].resize(chain[i].size() * 4 + 10);
    for (int i = 0; i < m; i++)
    {
        cin >> c >> x >> y;
        x--; y--;
        if (c == 'I')
        {
            y++;
            val[x] += y;
            int line = pos[x].first;
            modify(line, 0, 0, chain[line].size(), x);
        }
        else
        {
            if (fin[x] > fin[y])
                swap(x, y);
            int lca = unkey[findmin(0, 0, ord.size(), fin[x], fin[y] + 1)];
            cout << max(sum(x, lca), sum(y, lca)) << endl;
        }
    }

    return 0;
}