Root the tree and process postorder. dp[u][s] is the answer in u's subtree when u has boundary mode s; fold every child's states into u under parent-child compatibility rules.
Recognition signals
The input is a tree or a connected acyclic graph that can be rooted arbitrarily.
Removing the parent edge makes child subtrees conditionally independent.
Selecting a node constrains its parent, child, or neighbor.
A parent needs only a compact summary from each subtree.
The objective is a tree selection, cover, path, or count.
False friends
Signal
Why it is different
A cyclic general graph
One parent edge does not isolate subproblems; use graph DP, decomposition, or another method.
Only height or a simple sum
A single recursive aggregate is enough; multiple DP modes add no value.
A path may cross two children
A single undifferentiated answer cannot both represent the subtree optimum and a path extendable upward.
Core invariant
dfs(u,parent) returns the exact optimum for every boundary mode of u's subtree. Distinct child subtrees interact only through u and can therefore be folded independently.
State, transition, and processing order
Item
Definition
State
Node u, its parent, and a finite boundary mode for u; distinguish globally complete values from summaries extendable to the parent.
Transition
After all children return postorder, choose compatible child modes for each mode of u and aggregate by sum or extreme.
Frontier / order
Postorder DFS from any root, with parent preventing traversal back over an undirected edge.
Python skeleton
def max_non_adjacent(tree, values, root=0):
if not tree:
return 0
def dfs(u, parent):
skip, take = 0, values[u]
for v in tree[u]:
if v == parent: continue
child_skip, child_take = dfs(v, u)
take += child_skip
skip += max(child_skip, child_take)
return skip, take
return max(dfs(root, -1))
Correctness sketch
For a leaf, skip=0 and take=value are exact.
Once u's mode is fixed, child subtrees are independent: take forces each child to skip, while skip permits the child's better mode.
Induction proves both returned modes; the root has no parent restriction, so choose its better mode.
Complexity
Time
Space
Parameters
O(n·q²) for general compatibility, often O(n) for constant small q
O(n) stack/state
n is node count and q states per node.
Edge cases
empty tree
single node
negative weights and choosing none
skipping the parent edge
deep recursion
a forest needing a virtual root or components
Error patterns
Pattern
Why it fails / fix
Returning one value only
A parent's legal choice depends on the child's boundary mode; return every required mode.
Not skipping parent in an undirected tree
Recursion immediately cycles across the same edge.
Mixing global and upward path values
A path joining two children is complete and cannot continue upward as a whole.
Giving the chosen root special meaning
For an unrooted problem, explain why an arbitrary root preserves the answer.
Selection and exclusion rules
Check conditional independence after cutting the parent edge.
Encode only boundary information the parent needs.
Separate upward-returnable summaries from subtree-global answers.
Use iterative postorder on trees too deep for recursion.
Related templates
Relation
Template
Boundary
Original micro-example
Part
Detail
Result
The optimal selection is the two leaves with total 7.
Setup
A root has weight 5 and two leaves have weights 4 and 3; adjacent nodes cannot both be selected.
Trace
Taking the root yields 5; skipping it permits both leaves for 4+3=7.
Recall prompts
Why does tree DP usually return several modes?
Why can distinct child subtrees combine independently?
How does an upward path differ from a subtree-global path?