Path Queries with HLD

To query a path from $u$ to $v$:

$1.$ Find LCA of $u$ and $v$

$2.$ Query the path from $u$ to LCA

$3.$ Query the path from $v$ to LCA

For each path segment, climb chain by chain:

• While $u$ and $v$ 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 $O(\log n)$ chains are visited, so total time is $O(\log^2 n)$.