HLD Path Query - Code

Here's path maximum query:

function pathMax(u, v)
    result := -infinity
    while chainHead[u] ≠ chainHead[v]
        if depth[chainHead[u]] < depth[chainHead[v]] then
            swap(u, v)
        // Query from u to its chain head
        result := max(result, segmentTreeQuery(pos[chainHead[u]], pos[u]))
        u := parent[chainHead[u]]

    // Now u and v are in the same chain
    if depth[u] > depth[v] then
        swap(u, v)
    result := max(result, segmentTreeQuery(pos[u], pos[v]))
    return result

Time: $O(\log^2 n)$. The outer while loop runs $O(\log n)$ times, each iteration does an $O(\log n)$ segment tree query.