Heavy-Light decomposition

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

struct edge{
    int v;
    int w;
};

struct p_edge{
    int u;
    int w;
};

vector<p_edge> parent;
vector<vector<edge>> edges;
vector<int> chains;
vector<int> s;
vector<vector<int>> pathes;
vector<int> global;
vector<int> tree;
vector<vector<int>> up;
vector<int> tin, tout;
int timer = 0;
vector<int> position;

int n, N = 1, l = 1;

int calc_size(int u){
    int _size = 1;
    for (int i = 0; i < edges[u].size(); i++){
        _size += calc_size(edges[u][i].v);
    }
    s[u] = _size;
    return _size;
};

void hl_dfs(int u, int chain){
    if (chain == -1){
        chain = pathes.size();
        pathes.emplace_back();
    }

    chains[u] = chain;
    pathes[chain].push_back(u);

    if (edges[u].size() == 0)
        return;

    int v_max = 0, v_index;
    for (int i = 0; i < edges[u].size(); i++){
        if (s[edges[u][i].v] > v_max){
            v_max = s[edges[u][i].v];
            v_index = edges[u][i].v;
        }
    }

    hl_dfs(v_index, chain);
    for (int i = 0; i < edges[u].size(); i++)
        if (edges[u][i].v != v_index)
            hl_dfs(edges[u][i].v, -1);
}

void build_global_chain(){
    int p = 0;
    for (int i = 0; i < pathes.size(); i++){
        for (int j = 0; j < pathes[i].size(); j++){
            int v = pathes[i][j];
            if (v == 0) {
                position[v] = 0;
                global[p++] = -1;
            } else {
                position[v] = p;
                global[p++] = parent[v].w;
            }
        }
    }
}

void build_tree_up(int index, int value){
    tree[index] = value;
    if (!value) return;

    int parent = (index-1)/2;
    if (tree[parent] < tree[index])
        build_tree_up(parent, value);
}

void build_tree(){
    for (int i = 0; i < n; i++)
        build_tree_up(i+N-1, global[i]);
}

void dfs(int v, int p = 0){
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i < l; i++)
        up[v][i] = up[up[v][i-1]][i-1];
    for (int i = 0; i < edges[v].size(); i++)
        dfs(edges[v][i].v, v);
    tout[v] = ++timer;
}

bool upper(int u, int v){
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}

int lca(int a, int b){
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;

    for (int i = l-1; i >= 0; i--){
        if (!upper(up[a][i], b)){
            a = up[a][i];
        }
    }
    return up[a][0];
}

int find_on_path(int chain, int v){
    int l = 0, r = pathes[chain].size()-1, m;
    while (r-l > 1){
        m = (l+r)/2;
        if (pathes[chain][m] > v) r = m;
            else l = m;
    }
    if (pathes[chain][r] == v) return r;
    if (pathes[chain][l] == v) return l;
    return -1;
}

int get_maximum_on_path(int v, int _lca){
    int chain = chains[v];
    int bottom = find_on_path(chain, v);
    int top = find_on_path(chain, _lca);
    bool flag = !(top == -1);

    if (bottom == top)
        return std::numeric_limits<int>::min();

    bottom = N-1+position[pathes[chain][bottom]];
    top    = N-1+position[pathes[chain][top+1]];

    int maximum = tree[top];

    while (top != bottom){
        if (bottom/2 > top) {
            if (bottom%2 == 1){
                maximum = max(maximum, tree[bottom]);
                bottom--;
            } else
                bottom = (bottom-1)/2;
        } else {
            if (top%2 == 0){
                maximum = max(maximum, tree[top]);
                top++;
            } else
                top = (top-1)/2;

        }
    }
    maximum = max(maximum, tree[top]);

    if (flag) return maximum;
    return max(maximum, get_maximum_on_path(parent[pathes[chain][0]].u, _lca));
}

int get_maximum_between(int a, int b){
    int _lca = lca(a, b);
    return max(get_maximum_on_path(a, _lca),
               get_maximum_on_path(b, _lca)
               );
}

void dump_global_chain(){
    for (int i = 0; i < global.size(); i++)
        cout << global[i] << " ";
    cout << endl;
}

void dump_sizes(){
    for (int i = 0; i < s.size(); i++)
        cout << s[i] << " ";
    cout << endl;
}

void dump_chains(){
    for (int i = 0; i < pathes.size(); i++){
        cout << "Path #" << i + 1 << ": " << pathes[i][0];
        for (int j = 1; j < pathes[i].size(); j++)
            cout << " -> " << pathes[i][j];
        cout << endl;
    }
}

int main()
{
    cin >> n;
    while (N < n) { N *= 2; l++; };

    s.resize(n, 0);
    edges.resize(n);
    chains.resize(n, 0);
    global.resize(n, 0);
    parent.resize(n);
    tree.resize(2*N, std::numeric_limits<int>::min());
    tin.resize(n, 0);
    tout.resize(n, 0);
    position.resize(n, 0);

    up.resize(n);
    for (int i = 0; i < n; i++)
        up[i].resize(l, 0);

    // u - parent
    int u, v, w = 0;
    edge e;
    p_edge p;
    for (int i = 1; i < n; i++){
        cin >> u >> v >> w;
        e.v = v; e.w = w;
        p.u = u; p.w = w;
        edges[u].push_back(e);
        parent[v] = p;
    }
    parent[0].u = -1;
    parent[0].w = -1;

    calc_size(0);
    hl_dfs(0, -1);

    build_global_chain();
    build_tree();
    dfs(0);

    dump_sizes();
    dump_chains();
    dump_global_chain();

    int q, r;
    while (true){
        cin >> q >> r;
        cout << get_maximum_between(q, r) << endl;
    }

    return 0;
}