Worst Bridge on the Way — Solution & Editorial

Back to the Problem

Binary lifting storing, alongside each 2^j-ancestor, the maximum edge on that jump; an LCA walk combines the maxima of O(log N) jumps.

Complexity: O((N + Q) log N)