Heavy-Light Decomposition

```#include<bits/stdc++.h>
#define ll long long

// NOTE:
//      1-INDEXED

// Usage:
// HLD hld;
// hld.init(n);
// hld.decompose(root);
// build segment tree using inarray_inv[u]
// hld.getLCA(u, v)
// we can call getHLPath(u, v) to get all {from, to} path that we must walk through when travelling from u to v

struct HLD // Heavy Light Decomposition
{
int n;
int *sz;
int *next_heavy;
int *depth;
int *pa;
int *tail_heavy;
int *inarray; // inarray[u] is where node u-th resides in the array to make segment tree (tree-node to array-index)
int *inarray_inv; // use this to build/init segment tree (array-index to tree-node)

HLD() {};

void init(int n_) {
n = n_;

sz          = new int[n+1];
next_heavy  = new int[n+1];
depth       = new int[n+1];
pa          = new int[n+1];
tail_heavy  = new int[n+1];
inarray     = new int[n+1];
inarray_inv = new int[n+1];

fill(sz,         sz + n+1,          0);
fill(next_heavy, next_heavy + n+1, -1);
fill(depth,      depth + n+1,       0);
fill(pa,         pa + n+1,          0);
fill(tail_heavy, tail_heavy + n+1, -1);
fill(inarray,    inarray + n+1,    -1);
fill(inarray_inv,inarray_inv + n+1,-1);

}

void addEdge(int u, int v) {
}

void dfs(int u, int p) {
pa[u] = p;
sz[u] = 1;
depth[u] = depth[p] + 1;

int max_size = 0;
int best_child = -1;

for (auto v : adj[u]) if (v != p) {
dfs(v, u);
if (sz[v] > max_size) {
max_size = sz[v];
best_child = v;
}
sz[u] += sz[v];
}

if (best_child > 0) {
next_heavy[u] = best_child;
}

}

void dfs2(int u, int h, int &cnt) {
inarray[u] = cnt++;
inarray_inv[cnt-1] = u;

if (next_heavy[u] > 0) {
dfs2(next_heavy[u], h, cnt);
tail_heavy[u] = tail_heavy[next_heavy[u]];
}
else {
tail_heavy[u] = u;
}

if (v != pa[u] && v != next_heavy[u]) {
dfs2(v, v, cnt);
}

}

void decompose(int root) {
int cnt = 1;
depth[root] = 1;
dfs (root, 0);
dfs2(root, root, cnt);
}

int getLCA(int u, int v) {
while(u != v) {
if (depth[u] > depth[v])
swap(u, v);

v = u;
break;
}

else
}

return u;
}

void travelHL(int child, int parent, vector< pair<int, int> > & paths, bool include_parent) {
// get paths when travelling from a child to its parent

}

if (include_parent) {
paths.push_back({inarray[child], inarray[parent]});
}
else {
if (child != parent) {
int x = next_heavy[parent];
paths.push_back({inarray[child], inarray[x]});
}
}

}

vector< pair<int, int> > getHLPath(int u, int v) {
// returns a vector of {x, y} where we should travel from index x to index y in the ARRAY
// NOTE: we must call buildLCA() before calling this function

vector< pair<int, int> > paths;

int lca = getLCA(u, v);

travelHL(u, lca, paths, true);
travelHL(v, lca, paths, false);

return paths;

}

};

```