Path Queries II - Query Algorithm

For each query $(a, b)$, start at nodes $a$ and $b$. While they are in different chains, move the deeper one up. Query the segment from the deeper node to its chain head. Then jump to the parent of the chain head. When both are in the same chain, query the segment between them.

Track the maximum value across all queried segments. Return the maximum of all segments. This processes $O(\log n)$ segments, each queried in $O(\log n)$ time.

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