Graph Theory37 sections · 1633 units
Open in Course

When to Use Subtree DP

Problem recognition patterns

Use subtree DP when:

1.1. The input is a tree (acyclic, connected graph).

2.2. The problem asks for something aggregated (count, max, sum) over nodes or subtrees.

3.3. The answer for a node depends only on its descendants, not ancestors.

If you see these patterns, the approach is: define state on nodes, write recurrence combining children, implement DFS with post-order traversal. This structure solves most tree DP problems.