Graph Theory37 sections · 1633 units
Open in Course

Core Observation (Moving root changes distances)

(Distance shift insight)

When you move the root from node uu to its child vv, every distance in the tree shifts. Nodes inside vv's subtree are now 11 edge closer to the root. There are size[v] such nodes, so the total distance decreases by size[v].

Nodes outside vv's subtree are now 11 edge farther from the root. There are n - size[v] such nodes, so the total distance increases by n - size[v].

Combining both: answer[v] = answer[u] - size[v] + (n - size[v]) = answer[u] + n - 2 * size[v]. This single formula lets you compute every node's answer from its parent's answer in O(1)O(1).