Path Queries II - Implementation

Here is the HLD path query implementation:

function pathQueriesII(n, adj, values, queries):
    // Preprocess: HLD decomposition
    runHLD(n, adj)
    buildSegmentTree(values)

    function pathMax(u, v):
        result = -infinity

        while head[u] != head[v]:
            if depth[head[u]] < depth[head[v]]:
                swap(u, v)
            result = max(result, segTree.query(pos[head[u]], pos[u]))
            u = parent[head[u]]

        if depth[u] > depth[v]:
            swap(u, v)
        result = max(result, segTree.query(pos[u], pos[v]))

        return result

    function update(node, newValue):
        segTree.update(pos[node], newValue)

    for query in queries:
        if query.type == "max":
            print pathMax(query.u, query.v)
        else:
            update(query.node, query.value)

Time: $O(\log^2 n)$ per query. Space: $O(n)$.