To query a path from to :
Find LCA of and
Query the path from to LCA
Query the path from to LCA
For each path segment, climb chain by chain:
- While and are in different chains, query the chain containing the deeper node, then jump to the chain head's parent
- When in the same chain, query the range between them
Each chain query is a segment tree range query. At most chains are visited, so total time is .