DP on Trees & the Night Depots
In short: a tree DP solves leaves first and works up to the root, because a node's answer only depends on its children, and no two children's branches overlap. One number per node often isn't enough, since the parent may care about something the child can't see from a single best score — so each node returns one answer per state the parent cares about (here, a pair: the best demand if this depot is open, and if it's closed). The parent combines its children's pairs and hands its own pair further up.
Meridian's depots form a tree. The central hub supplies district depots, which supply local ones, and every depot has exactly one parent it gets its stock from. At night only some depots stay open. Two depots joined by a direct road share one night security patrol, so a depot and its parent can't both be open. Every depot has a different overnight demand. Which depots should open?
This is the grid problem again in a different shape. On a grid, a cell's answer came from the cells above and to the left. On a tree, a depot's answer comes from its children, and each child's answer is about its own branch, which no other branch overlaps. Solve the leaves first and work up to the root, and every branch is solved exactly once.
One number isn't enough
Try "the best demand in this depot's branch". Then the hub asks its child North: what's the best you can do? North says 6, but that 6 comes from North being open, and an open hub isn't allowed to use it. The child has to answer two questions, one for each thing the parent might do:
- take: the best demand in my branch if I'm open. Then all my
children must be closed:
demand + Σ child.skip. - skip: the best demand in my branch if I'm closed. Then each child
does whatever is better for it:
Σ max(child.take, child.skip).
The answer for the whole city is max(root.take, root.skip). Here it is on six
depots, with each depot badged t=take s=skip as the post-order sweep reaches
it:
Post-order fills every child's pair before its parent's, and the parent combines them. Demands are Hub 7, North 6, South 5, and 1 at each leaf.
Dock is a leaf. Open, it serves its demand of 1. Closed, it serves 0. Binary tree, 6 nodes, height 3. At node Dock.
The pair is what makes this work. Each child hands up one answer per state the parent cares about, and the parent never has to look further down than its own children.
The code handles any number of children, since the loop doesn't care. The pictures in this lesson use at most two per depot only so they fit on screen.
Predict a small one before you run anything:
def solve(node):
take, skip = node["demand"], 0
for child in node["children"]:
t, s = solve(child)
take += s
skip += max(t, s)
return take, skip
chain = {"demand": 4, "children": [{"demand": 5, "children": [{"demand": 4, "children": []}]}]}
print(max(solve(chain)))And one where you read the pair itself:
def solve(node):
take, skip = node["demand"], 0
for child in node["children"]:
t, s = solve(child)
take += s
skip += max(t, s)
return take, skip
leaf = lambda d: {"demand": d, "children": []}
star = {"demand": 5, "children": [leaf(2), leaf(2), leaf(2)]}
print(solve(star))Now it's your turn to break it. Someone "simplified" the take line:
The best legal plan opens the two ends for 8, but this prints 13, which means all three depots are open, including two linked pairs. Fix the line that lets an open depot count an open child.
Drawing your own sweep
Build the tree from dictionaries with left and right, so the drawing can
show it, and badge each depot the moment its pair is known. Change a demand, or
hang a new depot somewhere, and run it again:
Your post-order sweep. A depot's badge appears only after both of its children have theirs.
Choosing, not just scoring
The pairs give the best total, but the night plan needs names. Recover them top-down, the reverse of how the pairs were computed:
- The root has no parent, so it's free. It opens if
take > skip. - A depot whose parent opened must stay closed.
- A depot whose parent is closed is free, and opens if
take > skip.
A tie (take == skip) needs a rule, or two correct programs will print
different plans. The night depots rule is ties stay closed, because a closed
depot leaves its children free and costs nothing to staff.
Recursion depth is the one thing that can bite. A long chain of 5,000 depots is 5,000 nested calls, and Python stops at about 1,000. The fix is to number the depots so every parent comes before its children (a BFS order does this), then sweep the numbers backwards. Every child is then finished before its parent, with no recursion at all:
The same shape, flipped
The pair pattern handles any constraint between a node and its parent. Here's one where the rule points the other way, written as an interviewer would pose it:
Interview-style problem: fewest patrols. A patrol stationed at a depot watches every road touching that depot. Given the depot tree, return the fewest depots that need a patrol so that every road is watched from at least one end.
Constraints: up to 1,000 depots; the tree is given as nested
{"name", "demand", "children"}nodes, and demand is ignored.Examples: a chain of four depots →
2(the second and the third). A centre with four spokes →1. A single depot with no roads →0.
Before, an open depot forced its children closed. Now a depot without a
patrol forces every child to have one. The pair becomes
(fewest with a patrol here, fewest without), and the combine lines swap
roles. That's the build exercise.
❓ Cross-question: "What if the number of depots I can open is limited?" Then a pair isn't enough, and each depot returns a whole list: the best demand for every count of depots opened in its branch. Merging a child into its parent is then a knapsack step that splits the count between them. A knapsack inside a tree DP sounds exotic, but it's what the boss exercise asks for.
Why not just try every plan?
Each depot is open or closed, so there are 2ⁿ plans to check. The DP does a constant amount of work per depot. If checking one plan takes a microsecond:
| depots n | trying every plan |
|---|---|
| 20 | about 1 second |
| 30 | about 18 minutes |
| 37 | about 38 hours |
| 40 | about 13 days |
Every extra depot doubles it. The tree DP handles 37 depots in 37 steps, and a million depots in about a second. A small city already has more than 37 depots.
Each depot does a constant amount of work — combine its children's pairs once — and every depot is visited exactly once in the post-order sweep, so the whole DP is O(n) time. The state itself (one pair per node) costs O(n) space to store, and the recursion that computes it holds one stack frame per depot on the current root-to-leaf path, so the call stack also uses O(n) in the worst case — a long chain — which is exactly why the lesson's "sweep the numbers backwards" trick trades that stack for a plain array.
| Tree DP | State per node | Time |
|---|---|---|
| branch totals, deepest chain | one number | O(n) |
| night depots, fewest patrols | a pair (open / closed) | O(n) |
open at most B depots |
a list of B + 1 numbers |
O(n · B) with care |
| best headquarters (rerooting) | two sweeps, one number each | O(n) |
Idioms & real-world patterns
⚡ Advanced: rerooting
"Which depot should be headquarters, the one closest in total to every other?" Doing a tree DP from every depot costs O(n²). Rerooting does it in two sweeps. The first sweep, up from the leaves, finds the root's total and each branch's size. Then moving HQ across one road changes the total by a formula: the depots in the child's branch all get one road closer and everyone else gets one road further.
The capstone exercise does it with real road lengths, where the change is
km × (n − 2 · size).
The input is plain JSON
A tree arrives as nested dictionaries with a children list, which is what an
API or a config file would give you. Nothing needs a Node class, and the
grader compares plain values.
Quick practice
def solve(node):
take, skip = node["demand"], 0
for child in node["children"]:
t, s = solve(child)
take += s
skip += max(t, s)
return take, skip
def D(name, demand, *children):
return {"name": name, "demand": demand, "children": list(children)}
chain = D("A", 2, D("B", 9, D("C", 2, D("D", 9))))
print(max(solve(chain)))The best legal plan opens B and D for 9 + 9 = 18, but this prints 9 because the `take += s` line is missing, so an open depot never counts what its closed children were worth. Add the line back.
🎯 Your turn
Write night_depots(tree). Each node is {"name", "demand", "children"}. Open
depots so that no depot is open together with its direct parent, maximising
total demand. Return {"demand": total, "open": names_in_pre_order}.
- a hub (3) over Dock (2) and Mill (2) →
{"demand": 4, "open": ["Dock", "Mill"]}
Ties: decide from the root down. A depot opens only if its parent is closed
and its take is strictly greater than its skip.
Then press ▶ Run, tap the Live App try chips, and hit ✓ Check. Green means the night plan is built. ✅