Tree DP — Post-order DFS computing dp bottom-up

Maximum-weight independent set (House Robber III). At each node we keep two values: incl (best if the node is chosen) and excl (best if skipped). Leaves first, parents last.

step 0

Tree & current dp state

current node child being folded done
incl[v] = w[v] + Σ excl[child] excl[v] = Σ max(excl[child], incl[child])

dp table (excl, incl) per node

Answer = max(excl[root], incl[root]) = ?
Press Step to begin. We root the tree at node 0 and run a post-order DFS: every child is finished before its parent, so a parent can fold its children's (excl, incl) into its own.

Algorithm (the line we are executing)

function dfs(v, parent):           # post-order DFS
    excl = 0                          # best if v is NOT chosen
    incl = w[v]                       # best if v IS chosen
    for child c in adj[v]:
        if c == parent: continue      # don't walk back up
        dfs(c, v)                     # solve child's subtree first
        excl += max(excl[c], incl[c]) # child free to pick
        incl += excl[c]               # v chosen => child excluded
    return (excl, incl)               # summary for parent
# answer = max(dfs(root, -1))

Post-order processing

Nodes are folded leaves-first; each turns green when its (excl, incl) is final.

Invariant: when node v is processed, every child of v is already done, so dfs(c, v) returns instantly from the table. Each subtree is solved exactly once → O(n).
Self-contained visualization of dynamic programming on a tree. The recurrence is the classic include/exclude: a node that is included forces each child to its excl value; a node that is excluded lets each child take max(excl, incl). Each subtree is solved exactly once, so the whole DFS is O(n). See junior.md and professional.md for the correctness proof.