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. Subtrees stay contiguous too, and lca comes for free. 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[]: node u's value lives at pos[u].
// Subtree of u = positions [pos[u], pos[u] + sz[u] - 1].
struct HLD {
int n, timer = 0;
vector<vector<int>> adj;
vector<int> parent, depth, sz, heavy, head, pos;
HLD(vector<vector<int>>& g, int root = 0)
: n(g.size()), adj(g), parent(n, -1), depth(n), sz(n, 1),
heavy(n, -1), head(n), pos(n) {
dfs(root);
decompose(root, root);
}
void dfs(int u) {
for (int v : adj[u])
if (v != parent[u]) {
parent[v] = u, depth[v] = depth[u] + 1;
dfs(v);
sz[u] += sz[v];
if (heavy[u] == -1 || sz[v] > sz[heavy[u]]) heavy[u] = v;
}
}
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) inclusive ranges covering the u-v path,
// e.g. process_path(u, v, [&](int l, int r) { res = max(res, st.query(l, r + 1)); });
template <class F>
void process_path(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]); // for edge values use op(pos[u] + 1, pos[v])
}
int lca(int u, int v) {
for (; head[u] != head[v]; v = parent[head[v]])
if (depth[head[u]] > depth[head[v]]) swap(u, v);
return depth[u] < depth[v] ? u : v;
}
};