Graph Theory37 sections · 1633 units
Open in Course

Rerooting with Max (Not just sum)

(Maximum problems)

Sum-based rerooting is straightforward because addition is invertible: to exclude child vv, subtract vv's contribution. But max is not invertible. If the max came from child vv, removing vv does not give you the new max directly.

The fix: track the 22 largest child contributions. If you need to exclude the child that gave the maximum, use the second-largest instead. Store best1[u] and best2[u] during the down pass.

When computing up[v]: if vv contributed best1[u], use best2[u] as the sibling contribution. Otherwise use best1[u]. This keeps the up pass O(n)O(n) time and O(n)O(n) space.