heavy light decomposition

hld.hpp

#include "header.hpp"

class segtree {
public:
    constexpr static int n = 10005;
    int t[2*n];
    void set(int i,int v) {
        for(t[i+=n]=v;i>1;i>>=1)
            t[i>>1]=max(t[i], t[i^1]);
    }
    int get(int l,int r) {
        int a=0;
        for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
            if(l&1) a=max(a,t[l++]);
            if(r&1) a=max(a,t[--r]);
        }
        return a;
    }
};

class DecomposedTree { 
public:
    constexpr static int n = 10005;
private:   
    segtree values;
    int c2d[n], d2c[n], top[n], par[n], siz[n], dep[n], cid; 
    int dfs1(int node, int prev) {
        if(prev != -1) dep[n] = dep[prev]+1;
        else dep[n] = 1;
        par[node] = prev;
        siz[node] = 1;
        for(int& i:eli[node]) 
            if(i != prev) 
                siz[node] += dfs1(i, node);
        return siz[node];
    }
    void dfs2(int node, bool strong) {
        c2d[node] = cid;
        d2c[cid] = node;
        cid++;
        if(strong) { top[node] = top[par[node]]; }
        else { top[node] = c2d[node]; }
        if(eli[node].size() == 1) return;
        int mx = -1;
        for(int& i:eli[node]) 
            if(i != par[i] && (mx == -1 || siz[mx] < siz[i])) 
                mx = i;
        dfs2(mx, true);
        for(int& i:eli[node]) 
            if(i != par[i] && i != mx)
                dfs2(i, false);
    }
public:
    vector<int> eli[n];
    DecomposedTree() { }
    void initialize() {
        dfs1(1, -1);
        cid = 1;
        dfs2(1, false);
    }
    void update(int node, int val) {
        values.set(c2d[node], val);
    }

};