DP on Trees & Graphs

Where this sits relative to everything else

Every DP pattern so far has had a linear or grid-like state space — an index, a pair of indices, a range. This subtopic asks: what happens when the "positions" your DP moves between form a tree or a graph instead? The mechanics you already have — define a state, derive a transition, identify base cases — carry over completely unchanged. What's new is that the transition now needs to combine information from multiple children (for trees) or requires memoizing over an arbitrary DAG structure instead of a numeric index (for graphs). This is the natural convergence point of the Trees topic's traversal patterns and everything you've built in this topic — which is exactly why it's positioned last among DP subtopics.

DP on trees: extending "return info to parent"

Recall from the Trees topic that most non-trivial tree algorithms follow the same recursive shape: each call processes its subtree and returns information to its parent, which combines that information with its sibling's and its own. Diameter-of-tree and height-of-tree are the simplest examples of this — each recursive call returns a single number.

Tree DP is exactly this pattern, generalized to return multiple states per subtree instead of one value, because the parent needs to know more than just "the best answer within this subtree" — it needs enough information to make its own take/skip-style decision correctly.

The canonical shape: define your recursive function to return a small tuple — typically (best_if_this_node_is_included, best_if_this_node_is_excluded) or similar — computed from the same tuple returned by each child.

This is a direct tree-shaped generalization of the classic "non-adjacent selection" 1-D recurrence from DP Foundations — instead of "can't pick two adjacent array indices," the constraint becomes "can't pick a node and its direct child." The core insight — a node's decision depends on whether its neighbors (predecessors in the array, or parent/children in the tree) are also selected — is identical; only the shape of "neighbor" changed.

What's genuinely different from plain tree recursion

	Plain tree recursion (Trees topic)	Tree DP
Return value	Usually a single number/boolean (height, sum, whether balanced)	A small tuple of states (e.g. included/excluded, or per-color/per-status values)
Why more than one value	Not needed — the question has one answer per subtree	The parent's decision depends on information the single "best answer" alone doesn't capture (e.g. whether the child was included, not just the child's best value)
Combination step	Direct: sum/max of children's single return values	Sometimes a genuine knapsack-like combination: if a node can select at most k of its children to combine in some special way, you run a small knapsack over the children's (included, excluded) pairs rather than a fixed two-term formula
Overlapping subproblems?	No — each subtree is visited once regardless	No — same as plain recursion; the "memoization" here is really about carrying enough state, not revisiting nodes. Each node is still processed exactly once via post-order DFS

That last row is worth sitting with: tree DP on an actual tree rarely needs a memo cache at all, because a tree has no shared subproblems — each node has exactly one parent, so no subtree is ever recomputed. The "DP" here refers to the recurrence/combination structure (optimal substructure, explicit states), not to memoization defeating overlapping calls. That distinction flips once you move to DAGs, below.

When you do need extra passes: rerooting

Some tree problems ask for an answer at every node treated as the root (e.g. "for each node, the sum of distances to all other nodes") rather than a single global answer. A naive approach reruns a full O(n) traversal from each of the n nodes, costing O(n²). The fix — rerooting: run one post-order DFS to compute subtree-local information for an arbitrary root, then run a second pass that shifts the root from a parent to each child one edge at a time, updating the answer in O(1) per edge using the relationship between "how many nodes are in/out of this subtree." Two linear passes replace n separate traversals — a good example of how a second, cleverly-derived DFS pass can convert an apparently-quadratic tree problem into linear time.

DP on DAGs: memoized DFS on a graph

Once the underlying structure is a general graph rather than a tree — most commonly, a grid where moves are only allowed in a direction that strictly increases some value, which makes it an implicit DAG even though it's never described as a "graph" in the problem statement — the "each node has one parent" guarantee disappears. A cell can now be reachable via multiple paths, which means the same state genuinely gets recomputed unless you cache it. This is where memoization does real overlapping-subproblem-elimination work again, exactly as in the rest of this topic.

The "strictly increasing" constraint is what guarantees no cycles — without it, this would be a general graph and memoized DFS could infinite-loop. Recognizing that a monotonicity constraint in the problem statement (strictly increasing, strictly decreasing, or otherwise well-ordered) is what makes memoized DFS safe is the key transferable insight: it's the same acyclicity property that Topological Sort (from the Graphs topic) relies on, just discovered implicitly from the problem's structure rather than given explicitly as a DAG.

Comparison: tree DP vs. general graph/DAG DP

	Tree DP	DP on a general DAG
Can a state be reached more than one way?	No — exactly one path from root to any node	Yes — multiple paths can reach the same state
Is a memo cache doing real work?	Not really — more bookkeeping than optimization	Yes — essential, or you re-derive exponentially
Natural traversal	Post-order DFS (children before parent)	Memoized DFS, or Topological Sort + iterative relaxation
Typical state	A tuple per node (included/excluded, or similar)	A single best-value per node/cell, keyed by whatever uniquely identifies a state
Combination step complexity	Can require a small knapsack-like pass over children if only k of many children may be combined	Usually a simple max/min/sum over out-edges — the graph's structure carries less "choice" than a tree's arbitrary branching

Complexity

Tree DP: O(n) time and space for n nodes, since each node is visited once and does O(children) work — the total work across all nodes summed over all parent-child edges is O(n). If a node's combination step requires a knapsack-like pass over its c children (rather than a fixed-size combination), that node costs more than O(c) — watch for this in problems with an explicit "choose at most k children" constraint, where the total cost can grow to O(n × k) or worse depending on the combination. Rerooting: O(n) total across both passes, versus O(n²) for the naive per-node re-traversal. DAG DP: O(V + E) with memoization, since every state is computed exactly once and each computation does O(out-degree) work — identical in shape to a graph traversal from the Graphs topic, just with a cache added.

Common pitfalls

• Returning a single value when the parent needs more. If you can't decide the parent's answer without knowing whether a child was included, you need a tuple of states, not a single number — this is the single most common design mistake in tree DP.
• Forgetting the base case for None/absent children. An absent child should contribute a neutral value (0 for sum-like combinations, or explicit sentinel values matching your tuple shape) — get this wrong and leaf nodes compute incorrect results that silently propagate upward.
• Adding unnecessary memoization on an actual tree. Since no tree subproblem is ever revisited, wrapping tree DP in a memo dictionary keyed by node identity is usually wasted complexity (and can be actively wrong if you key by value instead of node identity when values repeat) — reserve explicit memoization for graphs/DAGs where recomputation is real.
• Missing the acyclicity guarantee on a graph problem. Applying memoized DFS to a graph that isn't actually a DAG (no monotonicity constraint ruling out cycles) can recurse infinitely — always verify (or explicitly construct, via Topological Sort) that the dependency structure is acyclic before trusting memoized DFS to terminate.
• Recomputing rerooting from scratch per node instead of deriving the O(1) edge-update. If your "second pass" redoes a full traversal for every node, you haven't actually applied rerooting — you've just reordered the same O(n²) work.