DP on trees: rerooting and subtree aggregates

Trees are the friendliest graphs for dynamic programming, and the reason is structural: a tree has no cycles, so once you root it, every subtree is a self-contained subproblem that never interferes with its siblings. One depth-first search computes any subtree aggregate by combining a node's children — dp[v] is built from dp[child].

The simplest is subtree size: sz[v] = 1 + Σ sz[c] over children c. A real DP in the same shape is maximum independent set on a tree — pick a set of vertices with no two adjacent, maximizing count or weight:

Read it: dp[v][1] takes v, so no child may be taken (dp[c][0]); dp[v][0] skips v, freeing each child to do whatever is best. One post-order DFS fills the whole table in O(n). This is the bread-and-butter pattern — count it once, root-down.

Now the trick that separates tree DP from the pack: rerooting. Suppose you need an answer rooted at every node — say, the sum of distances from each node to all others. Running a fresh DFS from each root is O(n²) and dies for n = 10⁵. Instead, solve it for one root, then slide the root along each edge in O(1), updating the answer as you go — a second DFS that re-roots from parent to child.

For sum-of-distances, moving the root from u to an adjacent v shifts every node: the sz[v] nodes on v's side each get one closer (−1 each), the remaining n − sz[v] nodes each get one farther (+1 each). So ans[v] = ans[u] + (n − 2·sz[v]) — a single arithmetic update per edge. Two DFS passes, O(n) total, all n answers.

Rerooting is the move to reach for whenever a problem asks for a per-node answer that looks like it needs n separate computations. The first DFS aggregates upward; the second pushes the global context downward. Almost every "for each node, considering the whole tree" problem is a rerooting in disguise.