Graph Theory37 sections · 1633 units
Open in Course

When to Use Rerooting (Problem patterns)

(All-roots signal)

If the problem statement says "for each node as root, compute X" or "compute X for all possible roots", consider rerooting. X could be sum of distances, maximum path length, number of good subtrees, diameter, etc. If you can define a tree DP recurrence for a single fixed root, you can probably extend it to all roots using rerooting.

The insight is defining down[v] and up[v] correctly. Core requirement: the answer for root vv must decompose into subtree contribution down[v] and outside contribution up[v]. If this decomposition exists, rerooting works.