Implementation - Path Query

To query the maximum on path from $u$ to $v$:

function path_query(u, v)
    res := -infinity
    while chain[u] != chain[v]
        if depth[head[u]] < depth[head[v]] then
            swap(u, v)
            res := max(res, seg_query(pos[head[u]], pos[u]))
            u := parent[head[u]]
            if depth[u] > depth[v] then
                swap(u, v)
                res := max(res, seg_query(pos[u], pos[v]))
                return res

This walks $O(\log n)$ chains, querying each one and tracking the maximum.

Space complexity is $O(n)$ for the data structures used.