DP on Trees

On a rooted tree, the natural subproblem is “the answer for the subtree of v”. Subtrees of different children do not overlap, and the subtree of v is just v plus its children’s subtrees. So:

• the state lives on vertices: dp[v], sometimes with a small extra flag;
• the order is post-order DFS: finish every child before its parent;
• each vertex combines its children’s values, so every edge is looked at once: O(n) in total.

The simplest example is subtree size: size[v] = 1 + Σ size[child]. Leaves have size 1, and the root gets n. It looks trivial, but sizes are used everywhere: counting pairs through an edge, finding a centroid, heavy-light decomposition.

Recursion is the easiest way to write it; for very deep trees (a path of 10⁵ vertices) use an explicit stack to avoid stack overflow.

On the example tree rooted at 4, the post-order fills leaves first (1, 0), then 1 gets (1, 1), 7 gets (2, 2), 3 gets (1, 1), 8 gets (2, 2), and the root gets take = 1 + 2 + 2 = 5, skip = 2 + 2 = 4. The answer is 5.

To list the vertices, walk down from the root: if v is allowed and take[v] ≥ skip[v], choose v and forbid its children; otherwise skip v and let the children decide for themselves. Here that picks {4, 6, 1, 3, 5}.

The same idea of two passes (up for values, down for choices) solves tree matching and minimum vertex cover. A second family, rerooting, adds a downward pass that passes “the answer from outside my subtree” to each child, so you can get, for example, the sum of distances from every vertex in O(n).