Graph Theory37 sections · 1633 units
Open in Course

Path Queries Using LCA

(Maximum, minimum, sum)

You can answer "what is the maximum edge weight on the path connecting u and v?" by splitting the path into two parts: u up to lca(u, v), and lca(u, v) down to v. For each node, precompute the maximum edge weight on the path to its ancestor 2i2^{i} steps above.

This extends binary lifting to carry edge weights. During LCA computation, you simultaneously compute the maximum edge weight encountered while climbing. This adds no extra queries.