Heavy-Light Decomposition
O(log² n) per path querySplits a tree into chains so that any root-to-node path crosses O(log n) of them, mapping each chain to a contiguous range of positions. Layer a segment tree over those positions and you can query or update values along any u–v path. The heavyweight tool for path queries on trees.
// use it on
CSES: Path Queries II ↗
Point updates and maximum on the path between two nodes: put node values at pos[u] in a max segment tree and fold it over each (l, r) range the decomposition yields.
// the code
// Pair with a segment tree over pos[] (e.g. max). Path values live at
// pos[u]. Recursive DFS: raise the stack limit or rewrite iteratively
// for n ~ 2e5 on judges with small stacks.
struct HLD {
int n, timer = 0;
vector<vector<int>> adj;
vector<int> parent, depth, heavy, head, pos;
HLD(vector<vector<int>>& g)
: n(g.size()), adj(g), parent(n, -1), depth(n),
heavy(n, -1), head(n), pos(n) {
dfs(0);
decompose(0, 0);
}
int dfs(int u) {
int size = 1, maxSub = 0;
for (int v : adj[u])
if (v != parent[u]) {
parent[v] = u, depth[v] = depth[u] + 1;
int sub = dfs(v);
size += sub;
if (sub > maxSub) maxSub = sub, heavy[u] = v;
}
return size;
}
void decompose(int u, int h) {
head[u] = h, pos[u] = timer++;
if (heavy[u] != -1) decompose(heavy[u], h); // chain continues
for (int v : adj[u])
if (v != parent[u] && v != heavy[u]) decompose(v, v);
}
// calls op(l, r) for O(log n) ranges covering the u-v path
template <class F>
void processPath(int u, int v, F op) {
for (; head[u] != head[v]; v = parent[head[v]]) {
if (depth[head[u]] > depth[head[v]]) swap(u, v);
op(pos[head[v]], pos[v]);
}
if (depth[u] > depth[v]) swap(u, v);
op(pos[u], pos[v]);
}
};