heavy_light_decomposition.cpp

// dont forget to construct
const ll N = 2e5;

vector<ll> h_paths[N], adj[N];
ll baap[N], h_num[N], h_loc[N], dpth[N], sub[N];
struct hld{
    ll n;

    hld(ll n): n(n) {
        for (ll i = 0; i < n; i++) {
            adj[i].clear();
            h_paths[i].clear();
            baap[i] = h_num[i] = h_loc[i] = -1;
            dpth[i] = 0;
        }
    }

    void add_edge(ll u, ll v){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void construct(ll root) {
        function<void(ll, ll)> dfs = [&](ll p, ll c)->void {
            baap[c] = p;
            sub[c] = 1LL;
            for (auto &ele: adj[c]) if (ele != p) {
                dpth[ele] = dpth[c] + 1;
                dfs(c, ele);
                sub[c] += sub[ele];
            }
        };
        dfs(-1, root);

        function<void(ll, ll)> dfs1 = [&](ll p, ll c)->void {
            for (auto &ele: adj[c]) if (ele != p) {
                if (sub[ele] > (sub[c] - 1) / 2) {
                    if (h_num[c] == -1) {
                        h_num[c] = c;
                        h_paths[c].push_back(c);
                    }
                    h_num[ele] = h_num[c];
                    h_loc[ele] = h_paths[h_num[ele]].size();
                    h_paths[h_num[c]].push_back(ele);
                }
                dfs1(c, ele);
            }
        };
        dfs1(-1, root);
    }

    ll lca(ll a, ll b) {
        if (dpth[a] < dpth[b]) swap(a, b);
        while (a != b) {
            if (h_num[a] == -1) {
                a = baap[a];
            }
            else {
                if (h_num[b] == h_num[a]) a = b;
                else if (dpth[h_num[a]]-1 >= dpth[b]) a = baap[h_num[a]];
                else if (h_num[b] == -1) b = baap[b];
                else if (dpth[h_num[b]] > dpth[h_num[a]]) b = baap[h_num[b]];
                else a = baap[h_num[a]];
            }

            if (dpth[a] < dpth[b]) swap(a, b);
        }
        return a;
    }
};