Heavy-Light Decomposition

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
int par[MAXN], dep[MAXN], sz[MAXN], heavy[MAXN];
int head[MAXN], pos[MAXN], timer;

void dfs(int u, int p, int d) {
    par[u] = p; dep[u] = d; sz[u] = 1; heavy[u] = -1;
    int mx = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u, d + 1);
        sz[u] += sz[v];
        if (sz[v] > mx) { mx = sz[v]; heavy[u] = v; }
    }
}

void decompose(int u, int h) {
    head[u] = h; pos[u] = ++timer;
    if (heavy[u] != -1) decompose(heavy[u], h);
    for (int v : adj[u])
        if (v != par[u] && v != heavy[u]) decompose(v, v);
}

void build(int root) {
    timer = 0;
    dfs(root, -1, 0);
    decompose(root, root);
}

vector<pair<int,int>> pathQuery(int u, int v) {
    vector<pair<int,int>> segs;
    while (head[u] != head[v]) {
        if (dep[head[u]] < dep[head[v]]) swap(u, v);
        segs.push_back({pos[head[u]], pos[u]});
        u = par[head[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    segs.push_back({pos[u], pos[v]});
    return segs;
}

pair<int,int> subtreeRange(int u) {
    return {pos[u], pos[u] + sz[u] - 1};
}