HLD.cpp

struct SegmentTree {
    vector<ll> t;
    int n; 

    inline ll ops(ll a, ll b) {return max(a,b);}

    SegmentTree(vector<ll> &a) {
        n = a.size();
        t.resize(2*n);
        for (int i = 0; i < n; i++)
            t[n + i] = a[i];   
        for (int i = n - 1; i >= 1; i--)
            t[i] = ops(t[2 * i],t[2 * i + 1]);
    }
 
    void update(int p, ll value)
    {
        for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = ops(t[p] , t[p^1]);
    }
 
    ll get( int l, int r)
    {
        ll res = LLONG_MIN;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l&1) res = ops(res, t[l++]);
            if (r&1) res = ops(t[--r], res);
        }
        return res;
    }
};

const int MAX = 2e5 + 7;
const int inf = 1e9 + 7;

int sz[MAX],in[MAX],rin[MAX],out[MAX],head[MAX],par[MAX];
vector<int>g[MAX];
vector<ll> tmp(10);
SegmentTree Tree(tmp);

void dfs_sz(int u,int p) {
    sz[u] = 1;
    par[u] = p;
    for(auto &v: g[u]) {
        if(v==p)continue;
        dfs_sz(v,u);
        sz[u] += sz[v];
        if(sz[v] > sz[g[u][0]])
            swap(v,g[u][0]);
    }
}

int t = 0;
void dfs_hld(int u,int p) {
    in[u] = ++t;
    rin[in[u]] = u;
    for(auto v: g[u]) {
        if(v==p)continue;
        head[v] = (v == g[u][0] ? head[u] : v);
        dfs_hld(v,u);
    }
    out[u] = t;
}
bool isParent(int p,int u){
    return in[p]<=in[u]&&out[u]<=out[p];
}
int n ;
int pathQuery(int u,int v){
    ll ret = -inf;
    for (int i=0; i<2; i++) {
        while(true){
            if(isParent(head[u],v))break;
            ret=max(ret,Tree.get(in[head[u]],in[u]) );
            u=par[head[u]];
        }
        swap(u,v);
    }
    if(in[v]<in[u])swap(u,v);
    ret = max(ret,Tree.get(in[u],in[v]));
    return ret;
}
void updateSubTree(int u,int val){
    Tree.update(in[u], val);//use lazy for subtree
}
void buildHLD(int root){
    dfs_sz(root,root);
    head[root]=root;
    dfs_hld(root,root);
}