A tree has no cycles, and that’s exactly what makes dynamic programming on it clean: each node’s answer depends only on its children’s answers, so a single post-order pass (children before parents) computes everything. Take the maximum-weight independent set — choose nodes with the largest total weight such that no two chosen nodes are adjacent. The trick is to keep two numbers at each node: the best total if you take it (then its children can’t be taken) and the best if you skip it (each child free to choose). Watch the two values flow up from the leaves and the optimal set light up.
O(n) — one post-order pass · two states per node · no-cycles = clean subproblems
independent set
A set of nodes with no two adjacent. Here we want the maximum total weight.
post-order
Process children before their parent, so a node’s subanswers are ready when needed.
take(v)
Best total for v’s subtree if v is chosen — add v, and all children must be skipped.
skip(v)
Best total for v’s subtree if v is not chosen — each child takes its own best.
tree-dp.js — take it, or skip it
Ready
A weighted tree. We compute, for every node, two values: take (best if we pick it) and skip (best if we don’t). Processing leaves first, each value comes from the children below. Step in post-order.
–
solving node
0/7
nodes done
–
max weight
How it works
The recurrence is short but complete. For a node v with weight w(v) and children c: if you takev, you gain w(v) but must skip every child, so take(v) = w(v) + Σ skip(c). If you skipv, each child is free to do whatever is best for it, so skip(v) = Σ max(take(c), skip(c)). A leaf has take = w and skip = 0. Because a tree has no cycles, these subtree answers never depend on each other circularly — one post-order pass fills them all, and the answer is max(take(root), skip(root)).
1
Start at the leaves
A leaf’s take value is just its own weight; its skip value is 0. Leaves have no children, so their answers are immediate.
2
Take = weight + children skipped
To take a node, add its weight and require every child to be skipped: take(v) = w(v) + Σ skip(c). Adjacent nodes can’t both be chosen.
3
Skip = children choose freely
If a node is skipped, each child independently contributes its better option: skip(v) = Σ max(take(c), skip(c)).
✓
Answer at the root
After the post-order pass reaches the root, the maximum-weight independent set is max(take(root), skip(root)). Trace the choices back down to recover which nodes are in it.
Time
O(n)
States / node
2 (take/skip)
Pass
one post-order
Why easy
no cycles
The code
# max-weight independent set on a tree, O(n)def solve(v, parent):
take = w[v] # take v: add its weight
skip = 0 # skip vfor c in children(v, parent):
t, s = solve(c, v) # post-order: child first
take += s # if v taken, children skipped
skip += max(t, s) # if v skipped, child picks bestreturn take, skip
t, s = solve(root, None)
answer = max(t, s) # best independent-set weight
Quick check
1. Why keep two values (take and skip) at each node?
Whether a node is taken changes what its children may do (taking it forbids taking any child). Carrying both the take and skip best-values lets the parent combine them correctly without recomputing.
2. What is take(v) in terms of the children?
If v is taken, no child can also be taken (they’re adjacent), so each child must contribute its skip value: take(v) = w(v) + Σ skip(c).
3. Why is dynamic programming on a tree so clean?
With no cycles, a node’s answer depends only on its subtree, and subtrees don’t overlap. So a single post-order pass computes every subproblem exactly once, in O(n).
FAQ
What is tree DP?
Dynamic programming on tree problems, where each node’s answer is computed from its children in one post-order pass (children before parents). A tree’s lack of cycles means subproblems are subtrees that never depend circularly, so it runs in linear time.
What is a maximum-weight independent set?
An independent set is a set of nodes with no two adjacent; the maximum-weight one has the largest total node weight. NP-hard on general graphs, but linear-time on trees via tree DP with a take/skip value per node.
How do you recover which nodes are in the optimal set?
Store both values, then trace down from the root: pick the larger of take/skip at the root. A taken node forces its children skipped; a skipped node lets each child pick its larger option. Following these decisions marks the optimal set.
What other problems use tree DP?
Subtree sizes/sums, tree diameter, tree colorings, minimum vertex cover and dominating set on trees, counting matchings, facility placement, and rerooting (an answer for every node as root). The pattern: combine children’s results at each node in a post-order pass.
SOLVE IT YOURSELF
Solve it: the best set of non-adjacent nodes
On a general graph this is NP-hard. On a tree it falls to one post-order pass, because each subtree only has to report two numbers upward. Python or TypeScript.
YOUR TASK
Implement max_independent_set(n, edges, weights): pick a set of nodes with no two adjacent, maximising total weight, and return that weight.
HINTS — 6 IDEAS
Each node reports two answers upward: the best total for its subtree including itself, and the best excluding itself.
include[u] = weight[u] + the sum of exclude[child] — taking u forbids every child.
exclude[u] = the sum of max(include[child], exclude[child]) — skipping u leaves each child free to choose.
Process children before parents. A post-order walk guarantees it; here that is a DFS pushing an order, then reading it in reverse.
The answer is max(include[root], exclude[root]).
Recursion is the obvious way to write this, but a deep path-shaped tree will blow the stack — the reference builds an explicit order instead, which is why the tests include a 1000-node chain.