Graph Theory37 sections · 1633 units
Open in Course

QTREE - Query Path Edges

(Exclude the LCA)

For edge queries, the path from aa to bb includes all edges between them, but not the edge above the LCA (because that edge is not on the path). During the path walk, when you reach the same chain, query from the deeper node to the LCA.

If the LCA itself would be included in the range, exclude it. If depth[a] > depth[b], query [pos[b]+1, pos[a]] to exclude node bb itself. This gets all edges on the path without counting the edge above the LCA.