Dynamic Programming on Trees

Dynamic programming works whenever a problem decomposes into overlapping subproblems ordered so that each can be solved from smaller ones already in hand. On a sequence the natural subproblems are prefixes; on an interval they are subintervals. On a tree the natural subproblems are rooted subtrees, and the ordering that makes them solvable is the post-order traversal, which visits every node only after all of its children. Root the tree anywhere, define an answer $f(v)$ for the subtree hanging below each node $v$, and a single depth-first sweep fills the entire table.

The defining feature of these problems is that the recurrence is local: the answer at $v$ depends only on the answers at $v$'s children,

never on grandchildren directly and never on the rest of the tree. Because the DFS touches each node and each edge exactly once and does $O(1)$ work per child, the whole computation runs in $\Theta (n)$ time for a tree on $n$ nodes.¹ The work is in choosing the state: what $f(v)$ must remember about the subtree so that a parent can combine children without re-descending into them. This is the usual optimal-substructure question, specialized to subtrees.

The archetype: maximum-weight independent set

Let each node $v$ of a tree carry a weight $w_v\ge 0$. An independent set is a set of nodes no two of which are adjacent; we want one of maximum total weight. On a general graph this is NP-hard, but on a tree dynamic programming solves it in linear time, the canonical illustration of the whole technique.²

The idea is to make the state record whether $v$ itself is used, because that is exactly the one fact a parent needs in order to decide about itself. Define, for the subtree rooted at $v$, two values:

• $dp[v][0]$, the best independent set of $v$'s subtree in which $v$ is not taken;
• $dp[v][1]$, the best one in which $v$ is taken.

If $v$ is not taken, each child $c$ is free to be taken or not, so we keep the better of its two options. If $v$ is taken, no child may be taken, so each child must contribute its $dp[c][0]$:

The base case falls out for free: a leaf has no children, so $dp[v][0]=0$ and $dp[v][1]=w_v$. The answer for the whole tree is $\max (dp[\text{root}][0],dp[\text{root}][1])$. This is House Robber III, where weights are the money in each house and the adjacency constraint forbids robbing a parent and its child on the same night.

Correctness is an induction on subtree size: assuming the recursive calls return correct pairs for every child, the two formulas above exhaust the only two choices for $v$ and combine each child's correct sub-answer optimally, so the returned pair is correct for $v$. The procedure visits each node once and spends $O(1)$ per child, hence $\Theta (n)$ total. The state, taken vs. not taken, is the part worth remembering: a single extra bit per node turns an intractable graph problem into a linear-time tree sweep.³

Paths through a node: diameter and maximum path sum

A second pattern arises when the quantity we care about is a path, not a set. The diameter of a tree is the number of edges on its longest path; the maximum path sum (where nodes carry values, possibly negative) is the largest total along any path. Neither is a clean subtree quantity, because the optimal path may bend at some node, descending into two different children.

The resolution is the signature move of tree DP on paths. At each node $v$, let $\text{down}(v)$ be the best downward path that starts at $v$ and goes into a single subtree. A child $c$ extends to $\text{down}(c)+(\text{edge or }{w}_v)$. The best path that bends at $v$ combines its two best children:

for the two children with the largest downward values. Here is the trap that catches everyone the first time:

For Binary Tree Maximum Path Sum the $\max (0,\cdot )$ prunes branches that would only hurt the total; the global $ans$ records the best bend seen anywhere. For Diameter of Binary Tree the same skeleton applies with edge counts in place of values: $\text{down}(v)=1+\max (\text{down}(\text{children}))$ and the diameter is the largest $\text{down}(c_1)+\text{down}(c_2)$ over all nodes $v$. Both run in $\Theta (n)$: one post-order pass, $O(1)$ per node.

Rerooting: an answer for every root in $O(n)$

The hardest variant asks for a quantity computed with each node in turn as the root: for every node $v$, say, the sum of distances from $v$ to all other nodes. Re-running an $O(n)$ DFS from each of the $n$ roots costs $O(n^2)$. Rerooting (also called the all-roots or re-root technique) computes all $n$ answers in $O(n)$ total, with two DFS passes: one down, one up.⁴

Take Sum of Distances in Tree. Fix an arbitrary root $r$ and let $S(v)$ be the number of nodes in $v$'s subtree and $D(v)$ the sum of distances from $v$ to every node inside its own subtree. A post-order pass computes both, since a child $c$ at distance $1$ contributes $D(c)+S(c)$ (every node under $c$ is one edge farther from $v$ than from $c$):

That gives the true global answer only at the root, where the subtree is the whole tree: $\text{ans}(r)=D(r)$. The second pass pushes the answer from a parent to each child in $O(1)$. Moving the root from $u$ to an adjacent child $v$, the $S(v)$ nodes on $v$'s side each get one closer (distance drops by $1$) and the remaining $n-S(v)$ nodes each get one farther:

Subtract the subtree's contribution, add the rest: the entire adjustment is a single $O(1)$ formula, so the down-pass plus the up-pass together are $\Theta (n)$.

A related linear-time tree DP is Distribute Coins in Binary Tree: each node returns to its parent the net coins it must send up or pull down, the signed excess $\text{coins}-1$ summed over its subtree, and the total number of moves is the sum of absolute flows along every edge, accumulated in one post-order pass. Same shape: a local return value, a global accumulator, $\Theta (n)$ time.

Takeaways

• On a tree, the natural DP subproblems are rooted subtrees, solved by a single post-order DFS that combines each node's children in $O(1)$, hence $\Theta (n)$ overall, since every node and edge is processed once.
• The state must capture exactly what a parent needs. For maximum-weight independent set (House Robber III) that is one bit, taken vs. not taken: $dp[v][0]={\sum }_c\max (dp[c][0],dp[c][1])$ and $dp[v][1]=w_v+{\sum }_{c}dp[c][0]$.
• The path-through-a-node pattern (diameter, max path sum) returns one thing and updates another: return the single best downward extension to the parent, but update a global max with the two-child bent path, never returning the bent path.
• Rerooting computes a per-root answer for all $n$ nodes in $O(n)$ via two passes: a down-pass fixes the root's answer from subtree aggregates, an up-pass transfers it edge-by-edge with a subtract my subtree, add the rest $O(1)$ adjustment.
• The recurring design questions are always the same: what does a node return to its parent, and what aggregate must the subtree cache so the combine stays $O(1)$.