For each query , start at nodes and . 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 segments, each queried in time.
Space complexity is for the data structures used.