Here is the HLD path query implementation:
function hldQuery(u, v):
result = -infinity
while head[u] != head[v]:
// Move the deeper chain head up
if depth[head[u]] < depth[head[v]]:
swap(u, v)
// Query from u to its chain head
result = max(result, segTree.query(pos[head[u]], pos[u]))
u = parent[head[u]]
// u and v are now on the same chain
if depth[u] > depth[v]:
swap(u, v)
// For edge weights, skip the LCA node
result = max(result, segTree.query(pos[u] + 1, pos[v]))
return result
function hldUpdate(edgeIndex, newWeight):
// Edge i stored at node edgeNode[i]
node = edgeNode[edgeIndex]
segTree.update(pos[node], newWeight)
Time: per query. Space: .