Graph Theory37 sections · 1633 units
Open in Course

Weighted Binary Lifting

(Carrying extra data)

In addition to up[v][i], store maxEdge[v][i] as the maximum edge weight on the path connecting v to up[v][i]. When equalizing depths or climbing together, update a running maximum: maxSoFar = max(maxSoFar, maxEdge[u][i]) whenever you jump u upward by 2i2^i. This extends binary lifting to answer path maximum queries in O(logn)O(\log n) per query.

You can also track minimum, sum, GCD, or any other aggregatable property along paths. The same preprocessing structure supports multiple types of queries. Build the tables once, then answer different query types using the same jumps.