Heavy light funfando

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <math.h>
#include <string.h>
#include <set>
#include <map>
#include <iostream>
#include <sstream>
#define MAXN 100001
#define ll long long

using namespace std;
using namespace std;

vector<vector<pair<int,int> > > g(MAXN);

int cnt[MAXN], prev[MAXN], chainNode[MAXN], chainHead[MAXN], posInChain[MAXN], base[MAXN], chainIdx = 0, idxSegTree = 0;

struct LCA{

    int H[MAXN], L[MAXN << 1], E[MAXN << 1], vis[MAXN], tree[MAXN * 8], idx;

    LCA(int root, int n){
        idx = 0;
        memset(H,-1,sizeof(H));
        memset(L,0,sizeof(L));
        memset(E,0,sizeof(E));
        memset(vis,0,sizeof(vis));
        dfs(root,0);
        build(1, 0, 2*n-1);
    }

    void dfs(int x, int depth){
        vis[x] = 1;//visited
        if(H[x] == -1) H[x] = idx;//mark first time the i'th node is visited
        L[idx] = depth;//when you visit a node you should mark the the depth you have found it.
        E[idx++] = x;//the i'th recursion, global variable
        for(int i = 0; i < g[x].size(); i++){
            int next = g[x][i].first;
            if(!vis[next]){
                dfs(next, depth+1);
                L[idx] = depth;
                E[idx++] = x;
            }
        }
    }

    //NlogN build the segtree and minimize the height of the I'th visited node
    void build(int node, int l, int r){
        if(l > r) return;
        if(l == r){
            tree[node] = l;
        }else{
            int mid = (l+r) >> 1;
            build(node*2, l, mid);
            build(node*2+1, mid+1, r);
            int A = tree[node*2];
            int B = tree[node*2+1];
            if(L[A] <= L[B]){
                tree[node] = A;
            }else{
                tree[node] = B;
            }
        }
    }

    //Get the vertex with the minimum height, then it will be the LCA of A and B.
    int rmq(int node, int l, int r, int ra, int rb){
        if(l > rb || r < ra){
            return -1;
        }else if(l >= ra && r <= rb){
            return tree[node];
        }else{
            int mid = (l+r) >> 1;
            int q1 = rmq(node*2, l, mid, ra, rb);
            int q2 = rmq(node*2+1, mid+1, r, ra, rb);
            if(q1 == -1){
                return q2;
            }else if(q2 == -1){
                return q1;
            }else{
                if(L[q1] <= L[q2]){
                    return q1;
                }else{
                    return q2;
                }
            }
        }
    }

    int getLCA(int u, int v, int n){
        int goFrom = H[u];
        int goTo = H[v];
        if(goFrom > goTo){
            swap(goFrom, goTo);
        }
        return E[rmq(1, 0, 2*n-1, goFrom, goTo)]; //is the LCA of A and B;
     }
};

struct SegTree{

    int tree[MAXN*4];

    void build(int node, int l, int r){
        if(l > r) return;
        if(l == r){
            tree[node] = l;
        }else{
            int mid = (l+r) >> 1;
            build(node*2, l, mid);
            build(node*2+1, mid+1, r);
            int A = tree[node*2];
            int B = tree[node*2+1];
            tree[node] = base[A] > base[B] ? A : B;
        }
    }

    int rmq(int node, int l, int r, int ra, int rb){
        if(l > rb || r < ra){
            return -1;
        }else if(l >= ra && r <= rb){
            return tree[node];
        }else{
            int mid = (l+r) >> 1;
            int q1 = rmq(node*2, l, mid, ra, rb);
            int q2 = rmq(node*2+1, mid+1, r, ra, rb);
            if(q1 == -1){
                return q2;
            }else if(q2 == -1){
                return q1;
            }else{
                return base[q1] > base[q2] ? q1 : q2;
            }
        }
    }

    void update(int node, int l, int r, int pos, int val){
        if(l > r) return;
        if(l == r && pos == r){
            tree[node] = val;
        }
        int mid = (l+r)/2;
        if(mid > pos){
            update(node*2, l, mid, pos, val);
        }else if(mid > pos){
            update(node*2+1, mid+1, r, pos, val);
        }
        tree[node] = max(tree[node*2], tree[node*2+1]);
    }
};

//Decompose the tree into chains
void HLD(int node, int cost, int parent){
    if(chainHead[chainIdx] == -1){
        chainHead[chainIdx] = node;
    }
    chainNode[node] = chainIdx;
    posInChain[node] = idxSegTree;
    base[idxSegTree++] = cost;
    int nodeHeavy = -1, nextCost;
    //seeking the special child (the one with most childs on the subtrees)
    for(int i = 0; i < g[node].size(); i++){
        int next = g[node][i].first;
        if(next != parent && (nodeHeavy == -1 || cnt[next] > cnt[nodeHeavy])){
            nodeHeavy = next;
            nextCost = g[node][i].second;
        }
    }
    if(nodeHeavy > -1){
        //expanding the current chain
        HLD(nodeHeavy, nextCost, node);
    }

    for(int i = 0; i < g[node].size(); i++){
        int next = g[node][i].first;
        if(next != nodeHeavy && next != parent){
            chainIdx++;
            HLD(next, g[node][i].second, node);
        }
    }

}

void dfsCnt(int node, int parent){
    cnt[node] = 1;
    for(int i = 0; i < g[node].size(); i++){
        int next = g[node][i].first;
        if(next != parent){
            prev[next] = node;
            dfsCnt(next, node);
            cnt[node] += cnt[next];
        }
    }
}

int walkChain(int U, int V, SegTree &q, int n){
    if(U == V) return 0;
    int ans = 0;
    while(chainNode[U] != chainNode[V]){
        int Left = posInChain[chainHead[chainNode[U]]];
        int Right = posInChain[U];
        int val = base[q.rmq(1, 0, n-1, Left, Right)];
        if(val > ans) ans = val;
        U = prev[chainHead[chainNode[U]]];
    }
    if(U == V) return ans;
    int val = base[q.rmq(1, 0, n-1, posInChain[V]+1, posInChain[U])];
    if(val > ans) ans = val;
    return ans;
}

int getMax(int U, int V, LCA &ref, SegTree &q, int n){
    int lca = ref.getLCA(U, V, n),a=0,b=0;
    if(lca != U)
        a = walkChain(U, lca, q, n);
    if(lca != V)
        b = walkChain(V, lca, q, n);
    return max(a,b);
}

void add(int a, int b, int c){
    g[a].push_back(make_pair(b,c));
    g[b].push_back(make_pair(a,c));
}

int main(void){
    int n = 14;
    add(0, 1, 1);
    add(0, 4, 3);
    add(0, 5, 1);
    add(1, 2, 2);
    add(1, 3, 2);
    add(4, 13, 11);
    add(5, 6, 3);
    add(5, 7, 6);
    add(5, 8, 2);
    add(7, 9, 1);
    add(7, 10, 4);
    add(10, 11, 2);
    add(10, 12, 3);
    memset(chainHead,-1,sizeof(chainHead));
    dfsCnt(0,-1);
    HLD(0,-1, -1);
    LCA lca(0,n);
    SegTree query;
    query.build(1,0,n-1);
    for(int i = 0; i < idxSegTree; i++) cout << base[i] << " ";
    return 0;
}