Tree DP & Rerooting
A company's org chart is a tree. You want to invite people to a party, but nobody enjoys a party their direct boss attends. Each person has a "fun" score. Whom do you invite? A network is a tree of routers. Where do you put the fewest monitors so that every cable has a monitor at one end? A file system is a tree of folders. How big is each folder, counting everything inside it? A city's road network happens to be a tree. For every intersection, what is the total walking distance to all the others?
All of these are tree DP problems. The table you fill is indexed by the tree's nodes. Each node's answer is built from its children's answers, so you fill it bottom-up: leaves first, root last. The last question, "for every intersection", adds a second pass called rerooting, which turns separate tree DPs into two linear sweeps.
In Grid DP every cell read one or two neighbours. In a tree, a node reads all of its children, and the number of children varies. That one change brings three new skills: folding an arbitrary number of children into one value, carrying several numbers per node ("with this node chosen" and "without"), and merging children's tables rather than single numbers (tree knapsack). The Tree Problem Patterns lesson previewed the idea with House Robber III; this lesson develops it fully.
You should be comfortable with DFS, the bottom-up "return values up" style from Tree Problem Patterns, and the state/transition/base-case vocabulary from DP Foundations.
Why this exists
Trees are the one kind of graph where "divide the problem into independent pieces" is free. Remove a node and its subtrees fall apart into pieces that share nothing. So the best answer for a node's subtree depends only on the best answers for its children's subtrees, plus a little information about how the node itself connects to them. That is optimal substructure, and the subproblems ("the subtree of ") number exactly .
Contrast that with general graphs. Maximum independent set (pick the heaviest set of vertices, no two adjacent) and minimum vertex cover (pick the fewest vertices touching every edge) are NP-hard on general graphs — no polynomial algorithm is known (Garey & Johnson, 1979). On a tree, both take with a two-number DP. Many NP-hard graph problems become easy on trees and, more generally, on graphs that are "tree-like" (small treewidth); Courcelle's theorem (1990) makes this precise for a whole logic of graph properties. Tree DP is the base case of that entire theory.
Rerooting has a more practical origin. Many problems ask for a value for every node as the root: total distance from every node, farthest node from every node, number of connected subgraphs containing every node. The naive answer runs the tree DP times, . Rerooting reuses the first DP and fixes it up as the root slides along each edge, in total. It is the same "upward pass, then downward pass" idea that powers belief propagation in probabilistic models (Pearl, 1982) and Felsenstein's pruning algorithm in phylogenetics (1981).
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "tree", " nodes and edges", "org chart", "hierarchy", "parent array" | Root it, then post-order DP |
| "choose nodes, no two adjacent", "no employee with their direct boss" | Max independent set: take[v], skip[v] |
| "every edge must have a guard / camera / monitor at an endpoint" | Min vertex cover: in[v], out[v] |
| "every node must be watched by itself or a neighbour" | Dominating set: three states per node (Binary Tree Cameras) |
| "longest path between any two nodes" | Diameter: top two child heights per node |
| "max path sum", path may bend at a node | Return the extendable part, track the bent part globally |
| "size of each subtree", "how many nodes below" | Subtree sizes: size[v] = 1 + Σ size[child] |
| "sum over all pairs of distances", "each edge is used by how many paths" | Edge contribution size · (n − size) |
| "pick exactly nodes that stay connected to the root", "courses with prerequisites, take " | Tree knapsack: merge children's tables, or |
| "for every node, compute …", "for each possible root" | Rerooting: down pass + up pass |
| "count colourings / subsets with a local rule, mod " | Counting tree DP with a state per colour |
| " up to " and recursion | Iterative DFS order, or raise the stack |
| "-th ancestor", "jump up levels" | Binary lifting: a DP over (power of two, node) |
The meta-trigger: the answer for a subtree depends only on the answers for its child subtrees plus how the root of the subtree is used. If "how the root is used" fits in a small number of states, tree DP works.
Intuition & first principles
The running example
We use one tree throughout. It has 7 nodes, numbered 0–6, with these edges: 0–1, 0–2, 1–3, 1–4, 2–5, 4–6. Each node has a value (the "fun score"), written in brackets.
graph TD
N0["0 (val 3)"] --> N1["1 (val 2)"]
N0 --> N2["2 (val 7)"]
N1 --> N3["3 (val 4)"]
N1 --> N4["4 (val 1)"]
N2 --> N5["5 (val 5)"]
N4 --> N6["6 (val 6)"]
Some vocabulary, defined once:
- A tree is a connected graph with no cycles. With nodes it has exactly edges, and there is exactly one simple path between any two nodes.
- Rooting the tree means picking one node (here 0) as the top. Then every other node has a parent (the next node on its path to the root) and possibly children.
- The subtree of , written , is plus everything below it. .
- A leaf has no children (3, 5, 6 here).
- Post-order means "a node after all its children". Any post-order of this tree, for example 3, 6, 4, 1, 5, 2, 0, is a valid fill order for tree DP.
The party problem, by hand
Pick a set of nodes with the largest total value such that no chosen node is the parent of another chosen node (no edge has both ends chosen). This is the maximum-weight independent set (MIS) on a tree. It is LeetCode's House Robber III and the classic "party at the company" problem.
Try greedy first. "Take the biggest values": 2 (7), then 6 (6), then 5 (5)? No — 5 is 2's child, so skip it. Then 3 (4): fine. Then 0 (3)? 0 is 2's parent. So greedy picks {2, 6, 3} = 17. Is that best? Not quite. {0, 3, 5, 6} = 3 + 4 + 5 + 6 = 18 is better: dropping the single big 7 lets us take both 0 and 5. Greedy cannot see this trade-off, because it is decided by the structure below and above node 2.
Now think locally. Stand at node 2. Two worlds:
- 2 is chosen. Then 5 cannot be. The best inside is .
- 2 is not chosen. Then 5 is free: take whichever is better for , which is "5 chosen" = 5. Total 5.
So reports two numbers to its parent: (with 2: 7, without 2: 5). The parent, node 0, needs both: if 0 is chosen it must use "without 2"; if not, it uses the better of the two. One number per subtree is not enough. Two numbers are, because the only thing the parent needs to know about a child's subtree is "is the child itself chosen?".
That is the whole recipe of tree DP:
- State: for each node, a small vector of numbers describing the best answer inside its subtree, one number per "way the node is used".
- Transition: combine the children's vectors.
- Order: post-order (children before parent).
- Answer: read it off the root's vector.
The two directions information can flow
graph TD
subgraph upward["Up pass: post-order, children to parent"]
U3["leaf 3"] --> U1["node 1"]
U4["node 4"] --> U1
U1 --> U0["root 0"]
end
subgraph downward["Down pass: pre-order, parent to children"]
D0["root 0"] --> D1["node 1"]
D1 --> D3["leaf 3"]
D1 --> D4["node 4"]
end
Most tree DPs only need the up pass: subtree answers flow from leaves to the root. Rerooting adds a down pass: once the root knows the answer for the whole tree, it hands each child "everything outside your subtree", and the child can compute its own whole-tree answer. Keep this picture; the last third of the lesson is about the down pass.
Recursion is natural — and dangerous
The cleanest code is recursive: solve(v) calls solve(child) for every child, then combines. That is post-order for free. The danger is depth. A tree can be a single long path (a "bamboo"). With , the recursion is calls deep. On the authoring machine a plain recursive tree DFS overflowed at depth about 4,500 in Node 24, about 17,000 in Java 21 (default stack), and Python stops at 1,000 unless you raise the limit. C++ with the default 8 MB stack handled depth but crashed (segmentation fault) at in an unoptimised build. Every implementation in this lesson therefore uses an iterative DFS order; section 8 below, "Iterative DFS and recursion limits", explains the trick and the alternatives.
Mechanics
0. Getting a post-order without recursion
All the DPs below share one preliminary step: compute a parent for every node and an order in which every parent comes before its children (a pre-order). Reversing it gives an order where every child comes before its parent — a valid post-order for DP purposes.
def preorder(adj, root=0):
parent = [-1] * len(adj)
order, stack = [], [root]
while stack:
v = stack.pop()
order.append(v)
for w in adj[v]:
if w != parent[v]: # in a tree, the only visited neighbour is the parent
parent[w] = v
stack.append(w)
return order, parent
On the running tree, with neighbours listed in edge order, this yields order = [0, 2, 5, 1, 4, 6, 3]. Reversed: [3, 6, 4, 1, 5, 2, 0]. Every node appears after all of its children. The DP loop then reads:
for v in reversed(order): # children before parents
...combine v's own data...
if parent[v] != -1:
...push v's finished result into parent[v]...
"Push into the parent" is often simpler than "pull from children": when we reach in reversed order, all of 's children have already pushed into it, so is finished and can push itself up.
The test `w != parent[v]` is enough only for trees
In a tree, the only already-visited neighbour of is its parent. If the input might contain a cycle or duplicate edges (it should not, if it is promised to be a tree), use a seen array instead.
1. Maximum independent set (House Robber III, "party")
State: take[v] = best total inside if is chosen; skip[v] = best total inside if is not chosen.
Transition:
Base: a leaf has take = val, skip = 0 (the sums are empty).
Order: post-order. Answer: max(take[root], skip[root]).
Trace on the running tree, in the order [3, 6, 4, 1, 5, 2, 0] (computed by the lesson's test script):
| Step | Node | Children (take, skip) | take = val + Σ skip | skip = Σ max | Pair |
|---|---|---|---|---|---|
| 1 | 3 | — (leaf) | 4 | 0 | (4, 0) |
| 2 | 6 | — (leaf) | 6 | 0 | (6, 0) |
| 3 | 4 | 6: (6, 0) | 1 + 0 = 1 | max(6, 0) = 6 | (1, 6) |
| 4 | 1 | 3: (4, 0), 4: (1, 6) | 2 + 0 + 6 = 8 | 4 + 6 = 10 | (8, 10) |
| 5 | 5 | — (leaf) | 5 | 0 | (5, 0) |
| 6 | 2 | 5: (5, 0) | 7 + 0 = 7 | 5 | (7, 5) |
| 7 | 0 | 1: (8, 10), 2: (7, 5) | 3 + 10 + 5 = 18 | 10 + 7 = 17 | (18, 17) |
The answer is . A brute force over all subsets agrees.
Getting the set back. Walk down in pre-order. The root is chosen if take ≥ skip (18 ≥ 17: chosen). A child of a chosen node is never chosen. A child of an unchosen node is chosen if its take > skip. Here: 0 chosen → 1 and 2 not chosen → 3: take 4 > 0, chosen; 4: take 1 < 6, not chosen → 6: parent 4 not chosen, take 6 > 0, chosen; 5: parent 2 not chosen, chosen. Result {0, 3, 5, 6}, total 18. Note how close the race at the root was: skipping 0 would give 17 via {2, 3, 6}.
2. Minimum vertex cover
A vertex cover is a set of nodes such that every edge has at least one end in the set ("every cable has a monitor at one end"). Find the smallest one.
State: in[v] = smallest cover of the edges inside with in the cover; out[v] = the same with not in the cover.
Transition: if is out, every edge – must be covered by , so every child must be in. If is in, those edges are covered, and each child does whatever is cheaper.
On the running tree (ignoring values): leaves 3, 6, 5 give (1, 0). Node 4: (1 + 0, 1) = (1, 1). Node 1: in = 1 + min(1,0) + min(1,1) = 2, out = 1 + 1 = 2. Node 2: (1, 1). Root 0: in = 1 + 2 + 1 = 4, out = 2 + 1 = 3. The minimum cover has 3 nodes, for example {1, 2, 4}: edges 0–1, 1–3, 1–4 (by 1), 0–2, 2–5 (by 2), 4–6 (by 4). Brute force agrees.
Two problems, one answer
In any graph, a set is a vertex cover exactly when its complement is an independent set (an edge with both ends outside would be uncovered). So minimum vertex cover = − maximum (unweighted) independent set. On our tree the largest independent set has 4 nodes (e.g. {0, 3, 5, 6}), and . ✔
Dominating set (every node is chosen or has a chosen neighbour; LeetCode's Binary Tree Cameras) needs three states per node: "has a camera", "no camera but covered by a child", "no camera and not yet covered (the parent must cover it)". The pattern is the same; only the bookkeeping grows.
3. Tree diameter via DP
The diameter is the number of edges on the longest path between any two nodes. Every path has a unique highest node (closest to the root), and from there it goes down into at most two different child subtrees. So:
State: down1[v] = longest downward path from (in edges); down2[v] = second longest, using a different child.
Transition: for each child , the candidate is down1[c] + 1; keep the top two.
Answer: .
| Node | Candidates from children | down1 | down2 | through |
|---|---|---|---|---|
| 3 | — | 0 | 0 | 0 |
| 6 | — | 0 | 0 | 0 |
| 4 | 6: 0 + 1 | 1 | 0 | 1 |
| 1 | 3: 1, 4: 2 | 2 | 1 | 3 |
| 5 | — | 0 | 0 | 0 |
| 2 | 5: 1 | 1 | 0 | 1 |
| 0 | 1: 3, 2: 2 | 3 | 2 | 5 |
The diameter is 5: 6 → 4 → 1 → 0 → 2 → 5. The binary-tree version of this, with , is traced in Tree Problem Patterns; this version works for any number of children. Weighted edges change + 1 into + w(v, c); with non-negative weights the alternative "BFS/DFS from any node to the farthest node , then from to the farthest node " also works, but it fails with negative weights, while the DP does not.
Max path sum (node values, possibly negative, path may bend) is the same shape: return the best extendable downward sum, and track the best bent sum globally. It is worked out in full in Tree Problem Patterns.
4. Subtree sizes and counting
The simplest tree DP of all: size[v] = 1 + Σ size[c]. On the running tree, size = [7, 4, 2, 1, 2, 1, 1] for nodes 0–6.
It is small, but it powers many counting arguments. The most useful one: an edge with the child lies on the path between and exactly when one of them is in and the other is not. There are size[c] · (n − size[c]) such pairs. So
On the running tree: (edge to 5) (to 6) (to 3) (to 4) (to 2) (to 1) . BFS from every node and halving the total also gives 50.
Counting DPs replace max/min with sums and products. Example (AtCoder Educational DP Contest P): paint each node white or black, with no two adjacent blacks; count the paintings. white[v] = Π (white[c] + black[c]), black[v] = Π white[c]. It is the MIS recurrence with + → × and max → +. This is the general principle: an optimisation tree DP and a counting tree DP share their state; only the semiring changes. See Counting DP for more.
5. Tree knapsack: merging tables
Now each node needs a whole array of states, not two numbers.
Problem. Choose exactly nodes so that the root is chosen and every chosen node's parent is also chosen (the chosen set is a connected piece hanging from the root — "to take a course you must take its prerequisite"). Maximise the total value.
State: dp[v][j] = best total choosing exactly nodes inside , with chosen and the set closed under "parent is chosen". Only makes sense.
Transition (merging one child at a time). Start with cur = [−∞, val[v]] (only itself). For each child , combine cur with dp[c], where the child may contribute nodes (skip its whole subtree) or nodes:
This is a (max, +) convolution of two arrays — the same "split a budget between two parts" step as in the 0/1 Knapsack lesson, except the "items" are whole subtrees.
graph LR
CUR["cur at v: j = 1..S nodes so far"] --> NEW["new: j = 1..S + s_c"]
CH["dp of child c: b = 0..s_c nodes"] --> NEW
Trace on the running tree (values [3, 2, 7, 4, 1, 5, 6]; − is , index from 0):
| Node | Merge step | Result dp[v] (j = 0, 1, 2, …) |
|---|---|---|
| 3 | leaf | [−, 4] |
| 6 | leaf | [−, 6] |
| 4 | [−, 1] ⊕ child 6 [−, 6] | [−, 1, 7] |
| 1 | [−, 2] ⊕ child 3 [−, 4] | [−, 2, 6] |
| 1 | [−, 2, 6] ⊕ child 4 [−, 1, 7] | [−, 2, 6, 9, 13] |
| 5 | leaf | [−, 5] |
| 2 | [−, 7] ⊕ child 5 [−, 5] | [−, 7, 12] |
| 0 | [−, 3] ⊕ child 1 [−, 2, 6, 9, 13] | [−, 3, 5, 9, 12, 16] |
| 0 | [−, 3, 5, 9, 12, 16] ⊕ child 2 [−, 7, 12] | [−, 3, 10, 15, 17, 21, 24, 28] |
Read the root's array: with the best is 15 = {0, 2, 5}; with , 10 = {0, 2}; with , 17 = {0, 1, 2, 5}. One detail of the last merge, : options are (9, from {0, 1, 3}), (5 + 7 = 12) and (3 + 12 = 15). A brute force over all valid subsets matches every entry.
Why it is , not
A naive bound says: nodes, each merge loops over arrays of length up to twice, so . That is far too pessimistic — if the loops run only up to the current sizes.
Merging child into costs about , where is the number of nodes merged into so far ( plus earlier children's subtrees) and . Read as the number of pairs with in the already-merged part and in . Each such pair has as its lowest common ancestor (LCA: the deepest node that is an ancestor of both). And each unordered pair of nodes is counted in exactly one merge: the merge at their LCA, at the moment the second of their two branches is merged in. So the total work is at most the number of pairs, , plus for the "" and "" terms:
On the running tree the Python code performs 32 inner-loop steps for ; pairs plus the column ( per merge, 11 in total) is exactly 32.
The bound depends on the loop limits
If you write for a in range(k+1): for b in range(k+1) at every merge, you pay per edge, , which is when . The pair-counting proof only works when the loops are bounded by the actual sizes of the two arrays.
With a cap :
If you only need , truncate every array to length and bound the loops by and . The total becomes . Proof sketch (a folklore argument, written up in several Codeforces community tutorials on tree knapsack): call a subtree big if it has more than nodes.
- Small–small merges: a node is paired with only while the merged component containing has at most nodes, so has partners in total. Sum: .
- Big–small merges cost ; each node sits in the small side of such a merge at most once (afterwards it is inside a big part). Sum: .
- Big–big merges cost . Each one reduces the number of disjoint big parts by one, and there are fewer than minimal big subtrees. Sum: .
6. Rerooting: the answer for every root
Problem. For every node , compute , the total distance from to all nodes (LeetCode 834, CSES Tree Distances II).
The naive approach runs a BFS from every node: . For that is steps. Rerooting does it in two passes.
Pass 1 (up, post-order) — answers for the root only. Root at 0. Compute size[v] and down[v] = :
(Every node in is one edge farther from than from , and there are size[c] of them.) Then .
Pass 2 (down, pre-order) — slide the root across each edge. Suppose we know and is a child of . Move the root from to . The size[c] nodes inside each get 1 closer. The other nodes each get 1 farther. So
graph LR
subgraph before["Root at p"]
P1["p"] --- C1["c with T(c): size[c] nodes"]
P1 --- R1["rest: n - size[c] nodes"]
end
subgraph after["Root at c"]
C2["c"] --- P2["p"]
C2 --- T2["T(c) nodes: each 1 closer"]
P2 --- R2["rest: each 1 farther"]
end
Trace. Pass 1 gives size = [7, 4, 2, 1, 2, 1, 1] and down = [11, 4, 1, 0, 1, 0, 0] (for node 1: distances to 1, 3, 4, 6 are 0 + 1 + 1 + 2 = 4). Pass 2, in pre-order [0, 2, 5, 1, 4, 6, 3], with :
| Step | Node | Parent | size[c] | ||
|---|---|---|---|---|---|
| 1 | 0 | — | — | 7 | down[0] = 11 |
| 2 | 2 | 0 | 11 | 2 | 11 + 7 − 4 = 14 |
| 3 | 5 | 2 | 14 | 1 | 14 + 7 − 2 = 19 |
| 4 | 1 | 0 | 11 | 4 | 11 + 7 − 8 = 10 |
| 5 | 4 | 1 | 10 | 2 | 10 + 7 − 4 = 13 |
| 6 | 6 | 4 | 13 | 1 | 13 + 7 − 2 = 18 |
| 7 | 3 | 1 | 10 | 1 | 10 + 7 − 2 = 15 |
Result for nodes 0–6. A BFS from each node gives the same seven numbers. Node 1 is the "most central" (total 10); leaf 5 is the most remote (19). As a cross-check, , twice the all-pairs sum from section 4.
7. The generic rerooting template (prefix/suffix of children)
Sum of distances had a lucky shortcut: moving the root changes the answer by a formula, because "+" can be undone ("subtract the child's contribution"). Many merges cannot be undone:
- max (farthest node from every node — CSES Tree Distances I, LeetCode 310). If the child you remove held the maximum, you cannot recover the second-largest from the max alone.
- product modulo a composite (AtCoder DP V "Subtree"). Dividing needs a modular inverse, which may not exist.
The general template avoids subtraction entirely. Describe the DP with four ingredients:
| Ingredient | Meaning | Farthest-node example | Connected-sets example |
|---|---|---|---|
identity | value of "no children" | 0 | 1 |
merge(a, b) | combine contributions (associative, commutative) | max | product mod |
lift(x) | turn a child's subtree value into a contribution for its parent (cross the edge) | (child's set, or nothing) | |
finalize(acc, v) | turn merged contributions at into 's subtree value | acc | acc |
Pass 1 (up): down[v] = finalize(merge over children c of lift(down[c]), v).
Pass 2 (down): define up[c] = the value of "the part of the tree outside ", seen as a subtree hanging below through its parent . Then 's neighbours in the rerooted tree are its children and , and
To compute up[c] we need 's value without child : everything at (its own parent side lift(up[p]) and all other children). Instead of "all minus ", build prefix and suffix merges over 's children list :
Each node's children are scanned a constant number of times, so both passes are merges in total.
graph LR
UPP["lift(up[p]) from above p"] --> EX["p without c_i"]
PRE["prefix: c_1 .. c_(i-1)"] --> EX
SUF["suffix: c_(i+1) .. c_m"] --> EX
EX -->|"finalize at p"| UPC["up[c_i]"]
In Python (this exact function is run by the lesson's tests on the farthest-node problem, the connected-sets problem and sum of distances, each checked against brute force):
def reroot(n, edges, identity, merge, lift, finalize, root=0):
"""Return ans[v] = DP value of the whole tree rerooted at v, for every v."""
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
parent, order, stack = [-1] * n, [], [root]
while stack: # iterative pre-order
v = stack.pop()
order.append(v)
for w in adj[v]:
if w != parent[v]:
parent[w] = v
stack.append(w)
children = [[w for w in adj[v] if w != parent[v]] for v in range(n)]
down = [None] * n
for v in reversed(order): # pass 1: post-order
acc = identity
for c in children[v]:
acc = merge(acc, lift(down[c]))
down[v] = finalize(acc, v)
up, ans = [None] * n, [None] * n
for v in order: # pass 2: pre-order
ch = children[v]
contrib = [lift(down[c]) for c in ch]
top = lift(up[v]) if parent[v] != -1 else identity
m = len(ch)
pre = [identity] * (m + 1)
for i in range(m):
pre[i + 1] = merge(pre[i], contrib[i])
suf = [identity] * (m + 1)
for i in range(m - 1, -1, -1):
suf[i] = merge(contrib[i], suf[i + 1])
ans[v] = finalize(merge(top, pre[m]), v)
for i, c in enumerate(ch): # everything at v except child c
up[c] = finalize(merge(top, merge(pre[i], suf[i + 1])), v)
return ans
On the running tree:
- Farthest node (
identity=0, merge=max, lift=x+1, finalize=acc):[3, 3, 4, 4, 4, 5, 5]. Nodes 0 and 1 have eccentricity 3, so they are the tree's centres (LeetCode 310's "minimum height trees" are exactly the nodes with the smallest eccentricity). - Connected sets containing , mod 6 (
identity=1, merge=product mod 6, lift=x+1, finalize=acc): the true counts are[21, 24, 16, 13, 18, 9, 10], so the answers mod 6 are[3, 0, 4, 1, 0, 3, 4]. Two answers are 0 mod 6, which is exactly why "divide out the child" is impossible here. - Sum of distances with pairs
(size, dist):identity=(0,0),mergeadds componentwise,lift((s,d)) = (s, d+s),finalize((s,d), v) = (s+1, d). The second components are[11, 10, 14, 15, 13, 19, 18], as before.
When you can subtract, do
If merge has an inverse (sums, XOR, products modulo a prime with no zero factors), up[c] is "total at minus 's contribution", and you can skip the prefix/suffix arrays. The sum-of-distances formula is that shortcut in closed form. For max, a lighter alternative to prefix/suffix is to keep the top two contributions at each node: if provided the best, use the second best.
8. Iterative DFS and recursion limits
Recursive tree DP on a path-shaped tree with nodes overflows in every one of our four languages unless you act. Options, best first:
- Order array + reverse loop (used in this lesson). One iterative DFS or BFS produces
orderandparent. Loopreversed(order)for the up pass andorderfor the down pass. No recursion at all, no state machine. BFS order works too: it also lists every parent before its children. - Explicit stack with a "children done" flag. Push
(v, False); when popped withFalse, push(v, True)and then the children; when popped withTrue, all children are finished, so combine. Use this when the work at must happen between children (for example, Euler tours that record entry and exit times). - Raise the limit. Language-specific, fragile, and sometimes forbidden by judges:
| Language | Default behaviour (authoring machine) | Raising it | Caveat |
|---|---|---|---|
| Python | RecursionError after 1,000 frames | sys.setrecursionlimit(10**6) | Before 3.12 a high limit could crash the process with a C-stack overflow; run recursion in a threading.Thread after threading.stack_size(...) for safety. Even when it works, Python recursion is slow. See Recursion & Induction. |
| Java | StackOverflowError near depth 17,000 for a tree DFS (1 MB default stack) | new Thread(null, task, "dfs", 1L << 28).start() or -Xss256m | The thread trick works on judges that forbid JVM flags. With a 1 GB thread stack, depth succeeded. |
| C++ | 8 MB main stack on Linux/macOS (ulimit -s); 1 MB default on Windows (MSVC) | ulimit -s unlimited (shell) or a linker flag | An unoptimised recursive DFS crashed between depth and here. |
| TypeScript / Node | RangeError: Maximum call stack size exceeded near depth 4,500 for a tree DFS | node --stack-size=... | Raising V8's limit beyond the OS thread stack causes a hard crash instead of an exception. Prefer iteration. |
`sys.setrecursionlimit` is not a stack
Python's limit is a counter; the OS thread stack is a separate, fixed-size block of memory. Older Pythons (and C extensions that recurse, like pickle and json) can segfault even under a raised limit. If a judge reports "runtime error" with no message on a deep tree, this is the first suspect.
9. Binary lifting: a DP over (power of two, node)
Tree DP is not only "one number per subtree". Binary lifting builds a table up[j][v] = the -th ancestor of with the recurrence
filled for . It is a DP whose states are (level , node ) and whose transition reads level twice. The same table can carry an aggregate along the jump (minimum edge weight, sum of values on the steps up), which answers path queries in . Full treatment, including LCA, is in LCA & Binary Lifting; the same doubling idea on graphs where every node has one outgoing edge appears in DAG DP as "DP on functional graphs".
The ladder: brute force → better → optimal
We climb two ladders: one for a single-root problem (maximum independent set) and one for an every-root problem (sum of distances).
Ladder A: maximum independent set
Rung 1 — try every subset. Enumerate subsets, keep the valid ones, take the best. . Useful only as a test oracle for ; it is how the lesson's examples were checked.
Rung 2 — recursion "take or skip " without memo. best(v, parentTaken): if the parent is taken, skip ; otherwise try both. Each call recurses into all children, and without memoization the same best(c, False) is recomputed for each choice at the parent. On a path the call tree branches, giving exponential time (Fibonacci-like growth).
Rung 3 — memoize best(v, parentTaken). There are states, each scanning its children: total. This is tree DP, written top-down. It still recurses, so depth is a risk.
Rung 4 — bottom-up pairs (take, skip) over an iterative post-order. Same , memory, no recursion, and the code is shorter.
Ladder B: answer for every root
Rung 1 — BFS from every node. . Fine for .
Rung 2 — run the tree DP once per root. Same , but generalises to any tree DP.
Rung 3 — rerooting with an invertible merge. Two passes, .
Rung 4 — generic rerooting with prefix/suffix. Two passes, merges, works for any associative merge. Slightly larger constant (prefix and suffix arrays per node).
| Rung | Method | Time | Extra space | Why better than the rung above |
|---|---|---|---|---|
| A1 | All subsets | Baseline oracle | ||
| A2 | Take/skip recursion, no memo | exponential | Only explores valid sets | |
| A3 | Memoized best(v, parentTaken) | + stack | Each of states solved once | |
| A4 | Bottom-up (take, skip) | No recursion, no stack overflow | ||
| B1 | BFS from every node | Baseline | ||
| B2 | Tree DP per root | Works for any tree DP | ||
| B3 | Reroot by formula | Reuses the first DP for every root | ||
| B4 | Generic reroot (prefix/suffix) | No inverse needed (max, mod-composite products) |
Correctness
Every tree DP proof is induction on subtree height (equivalently, on the post-order). Claim: when is processed, its state is correct for . Leaves are correct directly. For an inner node, its children were processed earlier and are correct by induction; the transition turns correct child states into a correct state for .
Maximum independent set. Independent sets of split into those containing and those not. If is in the set, no child is, and the rest of the set is an independent set inside each that avoids . The parts in different child subtrees never conflict, because no edge joins two different child subtrees (that would create a cycle through ). So the best is . If is not in the set, each child subtree is unconstrained and independent, giving . The "no edges between different child subtrees" fact is the heart of every tree DP; it is what lets the sums separate.
Minimum vertex cover. Same split. With out, each edge – must be covered by , forcing . With in, those edges are covered and children are free.
Diameter. Every simple path has a unique highest node ; from it descends into at most two distinct children. Its length is at most (the two longest descents through distinct children), and that value is achieved by an actual path. Maximising over covers all paths.
Tree knapsack. Valid sets in containing correspond to independent choices, one per child: either nothing from , or a valid set of containing . The size of the union is and its value is . Merging children one at a time is an induction over "the first children": after merging , cur[j] is the best total over sets using only and with exactly nodes. The (max, +) convolution step preserves that invariant.
Rerooting (sum of distances). Moving the root from to its child changes by for (the unique path from to passes through ) and by for every other (the unique path from to passes through ). Summing gives the formula. Pre-order guarantees is known before .
Rerooting (generic). In the tree rerooted at , the neighbours of are its old children and its old parent . The subtree hanging below through consists of , 's other children's subtrees and the part above — exactly what up[c] combines. By induction on depth, up[p] is correct when up[c] is computed (pre-order). Prefix/suffix give the merge over all children except without needing an inverse; associativity makes the grouping irrelevant, and commutativity lets the parent-side contribution be merged in any position.
Complexity
| Problem | Time | Space | Notes |
|---|---|---|---|
| Max independent set, vertex cover, counting colourings | Constant states per node | ||
| Dominating set (cameras) | Three states per node | ||
| Diameter / max path sum | Top two child values | ||
| Subtree sizes, pair-distance sum | |||
| Tree knapsack (all ) | worst case, arrays alive if you free children | Pair-counting argument | |
| Tree knapsack (cap ) | Loops bounded by | ||
| Rerooting, invertible merge | Two passes | ||
| Rerooting, prefix/suffix | merges | Each child list scanned three times | |
| Binary lifting table | levels |
All of these must at least read the tree, so is optimal for the first group. The tree knapsack's is tight for computing all : the output alone at the root has entries, and the merges genuinely look at pairs on balanced inputs.
Integer sizes. Sum of distances on a path of nodes reaches at an endpoint: overflow in 32 bits. Use 64-bit (long, long long); TypeScript's number is exact up to , which is enough here. The implementations below test exactly this case.
Implementation
One program per language. Each builds the running tree, runs maximum independent set (with the chosen set), sum of distances by rerooting, and tree knapsack with a cap , and asserts the numbers from this lesson. Each also builds a path of 200,000 nodes and checks the sum of distances from node 0, , which would overflow a recursive implementation's stack in every language. All four were run; the Python version was also checked against brute force on 300 random trees with up to 9 nodes.
from typing import List, Tuple
Edge = Tuple[int, int]
def build(n: int, edges: List[Edge]) -> List[List[int]]:
adj: List[List[int]] = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
return adj
def preorder(adj: List[List[int]], root: int = 0) -> Tuple[List[int], List[int]]:
"""Iterative DFS. Returns (order, parent); every parent precedes its children."""
parent = [-1] * len(adj)
order, stack = [], [root]
while stack:
v = stack.pop()
order.append(v)
for w in adj[v]:
if w != parent[v]:
parent[w] = v
stack.append(w)
return order, parent
def max_independent_set(n: int, edges: List[Edge], val: List[int]) -> Tuple[int, List[int]]:
"""Max total value of nodes with no two adjacent; returns (best, chosen nodes)."""
adj = build(n, edges)
order, parent = preorder(adj)
take = val[:] # take[v]: v chosen
skip = [0] * n # skip[v]: v not chosen
for v in reversed(order): # children are finished before v
p = parent[v]
if p != -1: # push v's finished pair into its parent
take[p] += skip[v]
skip[p] += max(take[v], skip[v])
chosen = [False] * n
for v in order: # walk down to recover one optimal set
p = parent[v]
if p == -1:
chosen[v] = take[v] >= skip[v]
else:
chosen[v] = (not chosen[p]) and take[v] > skip[v]
root = order[0]
return max(take[root], skip[root]), [v for v in range(n) if chosen[v]]
def sum_of_distances(n: int, edges: List[Edge]) -> List[int]:
"""ans[v] = sum of distances from v to every node, by rerooting."""
adj = build(n, edges)
order, parent = preorder(adj)
size = [1] * n
down = [0] * n # down[v]: sum of distances from v into its subtree
for v in reversed(order):
p = parent[v]
if p != -1:
size[p] += size[v]
down[p] += down[v] + size[v]
ans = [0] * n
for v in order: # parents before children
p = parent[v]
ans[v] = down[v] if p == -1 else ans[p] + n - 2 * size[v]
return ans
def tree_knapsack(n: int, edges: List[Edge], val: List[int], k: int) -> List[float]:
"""best[j] for j = 0..min(n, k): max value of j nodes containing root 0,
every chosen node's parent chosen. best[0] = -inf (the root is required)."""
NEG = float("-inf")
adj = build(n, edges)
order, parent = preorder(adj)
dp: List[List[float]] = [[] for _ in range(n)]
for v in reversed(order):
cur: List[float] = [NEG, val[v]] # cur[j]: j nodes chosen so far, v among them
for c in adj[v]:
if c == parent[v]:
continue
child = dp[c]
nxt = [NEG] * min(len(cur) + len(child) - 1, k + 1)
for a in range(1, len(cur)): # loops bounded by actual sizes
for b in range(len(child)):
if a + b > k:
break
cand = cur[a] + (0 if b == 0 else child[b])
if cand > nxt[a + b]:
nxt[a + b] = cand
cur = nxt
dp[c] = [] # free the child's table
dp[v] = cur
return dp[0]
if __name__ == "__main__":
n = 7
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (4, 6)]
val = [3, 2, 7, 4, 1, 5, 6]
best, chosen = max_independent_set(n, edges, val)
assert best == 18 and chosen == [0, 3, 5, 6]
assert sum_of_distances(n, edges) == [11, 10, 14, 15, 13, 19, 18]
assert tree_knapsack(n, edges, val, 7)[1:] == [3, 10, 15, 17, 21, 24, 28]
assert tree_knapsack(n, edges, val, 3)[3] == 15
big = 200_000 # a path: recursion would overflow
path = [(i, i + 1) for i in range(big - 1)]
d = sum_of_distances(big, path)
assert d[0] == big * (big - 1) // 2 == 19_999_900_000
print("all tree DP tests passed")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class TreeDP {
static List<List<Integer>> build(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
return adj;
}
/** Iterative DFS from 0: fills parent[], returns an order where parents precede children. */
static int[] preorder(List<List<Integer>> adj, int[] parent) {
int n = adj.size();
int[] order = new int[n], stack = new int[n];
int len = 0, top = 0;
Arrays.fill(parent, -1);
stack[top++] = 0;
while (top > 0) {
int v = stack[--top];
order[len++] = v;
for (int w : adj.get(v))
if (w != parent[v]) { parent[w] = v; stack[top++] = w; }
}
return order;
}
/** Returns best total; fills chosen[] with one optimal independent set. */
static long maxIndependentSet(int n, int[][] edges, int[] val, boolean[] chosen) {
List<List<Integer>> adj = build(n, edges);
int[] parent = new int[n];
int[] order = preorder(adj, parent);
long[] take = new long[n], skip = new long[n];
for (int i = 0; i < n; i++) take[i] = val[i];
for (int i = n - 1; i >= 0; i--) { // children before parents
int v = order[i], p = parent[v];
if (p != -1) {
take[p] += skip[v];
skip[p] += Math.max(take[v], skip[v]);
}
}
for (int v : order) { // recover the set top-down
int p = parent[v];
chosen[v] = p == -1 ? take[v] >= skip[v] : !chosen[p] && take[v] > skip[v];
}
return Math.max(take[0], skip[0]);
}
static long[] sumOfDistances(int n, int[][] edges) {
List<List<Integer>> adj = build(n, edges);
int[] parent = new int[n];
int[] order = preorder(adj, parent);
long[] size = new long[n], down = new long[n], ans = new long[n];
Arrays.fill(size, 1);
for (int i = n - 1; i >= 0; i--) {
int v = order[i], p = parent[v];
if (p != -1) { size[p] += size[v]; down[p] += down[v] + size[v]; }
}
for (int v : order) {
int p = parent[v];
ans[v] = p == -1 ? down[v] : ans[p] + n - 2 * size[v];
}
return ans;
}
static final long NEG = Long.MIN_VALUE / 4;
/** best[j], j = 0..min(n,k): max value of j nodes containing root 0, closed under parent. */
static long[] treeKnapsack(int n, int[][] edges, int[] val, int k) {
List<List<Integer>> adj = build(n, edges);
int[] parent = new int[n];
int[] order = preorder(adj, parent);
long[][] dp = new long[n][];
for (int i = n - 1; i >= 0; i--) {
int v = order[i];
long[] cur = {NEG, val[v]};
for (int c : adj.get(v)) {
if (c == parent[v]) continue;
long[] child = dp[c];
long[] nxt = new long[Math.min(cur.length + child.length - 1, k + 1)];
Arrays.fill(nxt, NEG);
for (int a = 1; a < cur.length; a++)
for (int b = 0; b < child.length && a + b <= k; b++) {
long cand = cur[a] + (b == 0 ? 0 : child[b]);
if (cand > nxt[a + b]) nxt[a + b] = cand;
}
cur = nxt;
dp[c] = null; // free the child's table
}
dp[v] = cur;
}
return dp[0];
}
public static void main(String[] args) {
int n = 7;
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {4, 6}};
int[] val = {3, 2, 7, 4, 1, 5, 6};
boolean[] chosen = new boolean[n];
check(maxIndependentSet(n, edges, val, chosen) == 18);
check(Arrays.equals(chosen, new boolean[]{true, false, false, true, false, true, true}));
check(Arrays.equals(sumOfDistances(n, edges), new long[]{11, 10, 14, 15, 13, 19, 18}));
long[] best = treeKnapsack(n, edges, val, 7);
check(Arrays.equals(Arrays.copyOfRange(best, 1, 8), new long[]{3, 10, 15, 17, 21, 24, 28}));
check(treeKnapsack(n, edges, val, 3)[3] == 15);
int big = 200_000; // a path: recursion would overflow
int[][] path = new int[big - 1][];
for (int i = 0; i + 1 < big; i++) path[i] = new int[]{i, i + 1};
check(sumOfDistances(big, path)[0] == 19_999_900_000L);
System.out.println("all tree DP tests passed");
}
static void check(boolean ok) {
if (!ok) throw new AssertionError("test failed");
}
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
using Edges = vector<pair<int, int>>;
vector<vector<int>> build(int n, const Edges& edges) {
vector<vector<int>> adj(n);
for (auto [a, b] : edges) {
adj[a].push_back(b);
adj[b].push_back(a);
}
return adj;
}
// Iterative DFS from 0: fills parent, returns an order where parents precede children.
vector<int> preorder(const vector<vector<int>>& adj, vector<int>& parent) {
int n = adj.size();
parent.assign(n, -1);
vector<int> order, stack = {0};
order.reserve(n);
while (!stack.empty()) {
int v = stack.back();
stack.pop_back();
order.push_back(v);
for (int w : adj[v])
if (w != parent[v]) { parent[w] = v; stack.push_back(w); }
}
return order;
}
long long maxIndependentSet(int n, const Edges& edges, const vector<int>& val,
vector<bool>& chosen) {
auto adj = build(n, edges);
vector<int> parent;
auto order = preorder(adj, parent);
vector<long long> take(val.begin(), val.end()), skip(n, 0);
for (int i = n - 1; i >= 0; --i) { // children before parents
int v = order[i], p = parent[v];
if (p != -1) {
take[p] += skip[v];
skip[p] += max(take[v], skip[v]);
}
}
chosen.assign(n, false);
for (int v : order) { // recover one optimal set
int p = parent[v];
chosen[v] = p == -1 ? take[v] >= skip[v] : !chosen[p] && take[v] > skip[v];
}
return max(take[0], skip[0]);
}
vector<long long> sumOfDistances(int n, const Edges& edges) {
auto adj = build(n, edges);
vector<int> parent;
auto order = preorder(adj, parent);
vector<long long> size(n, 1), down(n, 0), ans(n, 0);
for (int i = n - 1; i >= 0; --i) {
int v = order[i], p = parent[v];
if (p != -1) { size[p] += size[v]; down[p] += down[v] + size[v]; }
}
for (int v : order) {
int p = parent[v];
ans[v] = p == -1 ? down[v] : ans[p] + n - 2 * size[v];
}
return ans;
}
const long long NEG = LLONG_MIN / 4;
// best[j], j = 0..min(n,k): max value of j nodes containing root 0, closed under parent.
vector<long long> treeKnapsack(int n, const Edges& edges, const vector<int>& val, int k) {
auto adj = build(n, edges);
vector<int> parent;
auto order = preorder(adj, parent);
vector<vector<long long>> dp(n);
for (int i = n - 1; i >= 0; --i) {
int v = order[i];
vector<long long> cur = {NEG, val[v]};
for (int c : adj[v]) {
if (c == parent[v]) continue;
const auto& child = dp[c];
vector<long long> nxt(min(cur.size() + child.size() - 1, (size_t)k + 1), NEG);
for (int a = 1; a < (int)cur.size(); ++a)
for (int b = 0; b < (int)child.size() && a + b <= k; ++b) {
long long cand = cur[a] + (b == 0 ? 0 : child[b]);
nxt[a + b] = max(nxt[a + b], cand);
}
cur = std::move(nxt);
vector<long long>().swap(dp[c]); // free the child's table
}
dp[v] = std::move(cur);
}
return dp[0];
}
int main() {
int n = 7;
Edges edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {4, 6}};
vector<int> val = {3, 2, 7, 4, 1, 5, 6};
vector<bool> chosen;
assert(maxIndependentSet(n, edges, val, chosen) == 18);
assert((chosen == vector<bool>{true, false, false, true, false, true, true}));
assert((sumOfDistances(n, edges) == vector<long long>{11, 10, 14, 15, 13, 19, 18}));
auto best = treeKnapsack(n, edges, val, 7);
assert((vector<long long>(best.begin() + 1, best.end()) ==
vector<long long>{3, 10, 15, 17, 21, 24, 28}));
assert(treeKnapsack(n, edges, val, 3)[3] == 15);
int big = 200000; // a path: recursion would overflow
Edges path;
for (int i = 0; i + 1 < big; ++i) path.push_back({i, i + 1});
assert(sumOfDistances(big, path)[0] == 19999900000LL);
cout << "all tree DP tests passed\n";
return 0;
}
type Edge = [number, number];
function build(n: number, edges: Edge[]): number[][] {
const adj: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
adj[a].push(b);
adj[b].push(a);
}
return adj;
}
// Iterative DFS from 0: returns [order, parent]; parents precede children in order.
function preorder(adj: number[][]): [number[], number[]] {
const n = adj.length;
const parent: number[] = new Array(n).fill(-1);
const order: number[] = [];
const stack: number[] = [0];
while (stack.length > 0) {
const v = stack.pop()!;
order.push(v);
for (const w of adj[v])
if (w !== parent[v]) {
parent[w] = v;
stack.push(w);
}
}
return [order, parent];
}
function maxIndependentSet(n: number, edges: Edge[], val: number[]): [number, number[]] {
const [order, parent] = preorder(build(n, edges));
const take = val.slice();
const skip: number[] = new Array(n).fill(0);
for (let i = n - 1; i >= 0; i--) { // children before parents
const v = order[i], p = parent[v];
if (p !== -1) {
take[p] += skip[v];
skip[p] += Math.max(take[v], skip[v]);
}
}
const chosen: boolean[] = new Array(n).fill(false);
for (const v of order) { // recover one optimal set
const p = parent[v];
chosen[v] = p === -1 ? take[v] >= skip[v] : !chosen[p] && take[v] > skip[v];
}
const picked: number[] = [];
for (let v = 0; v < n; v++) if (chosen[v]) picked.push(v);
return [Math.max(take[0], skip[0]), picked];
}
function sumOfDistances(n: number, edges: Edge[]): number[] {
const [order, parent] = preorder(build(n, edges));
const size: number[] = new Array(n).fill(1);
const down: number[] = new Array(n).fill(0);
const ans: number[] = new Array(n).fill(0);
for (let i = n - 1; i >= 0; i--) {
const v = order[i], p = parent[v];
if (p !== -1) {
size[p] += size[v];
down[p] += down[v] + size[v];
}
}
for (const v of order) {
const p = parent[v];
ans[v] = p === -1 ? down[v] : ans[p] + n - 2 * size[v];
}
return ans;
}
// best[j], j = 0..min(n,k): max value of j nodes containing root 0, closed under parent.
function treeKnapsack(n: number, edges: Edge[], val: number[], k: number): number[] {
const adj = build(n, edges);
const [order, parent] = preorder(adj);
const dp: number[][] = new Array(n);
for (let i = n - 1; i >= 0; i--) {
const v = order[i];
let cur: number[] = [-Infinity, val[v]];
for (const c of adj[v]) {
if (c === parent[v]) continue;
const child = dp[c];
const nxt: number[] = new Array(Math.min(cur.length + child.length - 1, k + 1)).fill(-Infinity);
for (let a = 1; a < cur.length; a++)
for (let b = 0; b < child.length && a + b <= k; b++) {
const cand = cur[a] + (b === 0 ? 0 : child[b]);
if (cand > nxt[a + b]) nxt[a + b] = cand;
}
cur = nxt;
dp[c] = []; // free the child's table
}
dp[v] = cur;
}
return dp[0];
}
function assert(ok: boolean, msg = "test failed"): void {
if (!ok) throw new Error(msg);
}
const same = (x: unknown, y: unknown): boolean => JSON.stringify(x) === JSON.stringify(y);
const n = 7;
const edges: Edge[] = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [4, 6]];
const val = [3, 2, 7, 4, 1, 5, 6];
const [best, chosen] = maxIndependentSet(n, edges, val);
assert(best === 18 && same(chosen, [0, 3, 5, 6]));
assert(same(sumOfDistances(n, edges), [11, 10, 14, 15, 13, 19, 18]));
assert(same(treeKnapsack(n, edges, val, 7).slice(1), [3, 10, 15, 17, 21, 24, 28]));
assert(treeKnapsack(n, edges, val, 3)[3] === 15);
const big = 200_000; // a path: recursion would overflow
const path: Edge[] = [];
for (let i = 0; i + 1 < big; i++) path.push([i, i + 1]);
assert(sumOfDistances(big, path)[0] === 19_999_900_000);
console.log("all tree DP tests passed");
A note on the knapsack code in all four languages: the inner loop runs a up to the current array length and b up to the child's array length, and the arrays are truncated to entries. Those two choices are precisely what the and proofs need. Freeing each child's table after merging keeps memory proportional to the arrays still waiting to be merged.
Real-world uses
- Compilers: instruction selection by tree tiling. A compiler's intermediate code for an expression is a tree; the machine's instructions are "tiles" that cover tree patterns, each with a cost. Picking the cheapest tiling is a bottom-up tree DP: the best cost for a node is the minimum over tiles rooted there of the tile cost plus the best costs of the subtrees left uncovered. Aho, Ganapathi and Tjiang, "Code generation using tree matching and dynamic programming" (ACM TOPLAS 11(4), 1989), and the iburg/BURS generators used in LCC are built on exactly this.
- Phylogenetics. Felsenstein's pruning algorithm (1981) computes the likelihood of DNA data on an evolutionary tree by a post-order DP over the tree: each node stores, for each nucleotide, the probability of the data below it. Sankoff's small-parsimony algorithm (1975) is the min-cost version. Programs such as RAxML and PhyML run this DP millions of times per analysis.
- Belief propagation on trees. In a tree-shaped probabilistic graphical model, exact marginals for every variable come from one upward and one downward pass of messages (Pearl, 1982). That is rerooting: the downward message to a child is "everything except that child", often computed with exactly the prefix/suffix trick when division is unstable.
- Network placement. Placing proxies, caches or monitors in a tree-shaped network to minimise access cost is solved by tree DP; for example Li, Golin, Italiano, Deng and Sohraby, "On the optimal placement of web proxies in the Internet" (IEEE INFOCOM 1999), place proxies on a tree-shaped network with a dynamic program over subtrees — a tree knapsack in spirit.
- UI layout. Layout engines walk the widget or DOM tree: constraints go down, sizes come up. Flutter's documentation summarises its protocol as "Constraints go down. Sizes go up. Parent sets position." The "sizes go up" half is a subtree DP.
- Disk usage and aggregations.
ducomputes folder sizes bottom-up; databases computing rollups over a category hierarchy, and organisation charts summing headcount by department, are all subtree-sum DPs.
Pitfalls & edge cases
- Recursion depth. A path of nodes overflows default stacks. Use the order-array approach or raise the stack deliberately.
- Assuming the input is rooted at 0, or that node 's parent is smaller than . Many problems give an edge list in arbitrary order. Root it yourself.
- Forgetting the single-node tree. : no edges, MIS = val[0], diameter 0, sum of distances [0]. Make sure your loops tolerate an empty edge list.
- Taking
max(take, skip)at the root but reconstructing with a different tie-break. Use one rule consistently in both the DP and the walk down. - Knapsack loops bounded by or instead of current sizes. Correct answers, time. See the warning above.
- Knapsack: leaving index 0 of a child as "0" instead of handling "take nothing" separately. With the "root must be chosen" state,
dp[c][0]is (impossible), while "skip the child's whole subtree" is a separate option worth 0. Mixing them up either forbids skipping or allows choosing a node without its parent. - Rerooting with subtraction on a non-invertible merge. Max and products mod a composite cannot be "undone". Use prefix/suffix or top-two.
- Rerooting formula for the wrong direction. uses the size of the child side computed when rooted at the original root. If you reroot twice, recompute or reason carefully.
- Overflow. Distance sums on paths exceed around .
- Using
w != parent[v]on a graph that is not actually a tree (duplicate edges, a cycle): the DFS loops forever or double-counts. Validate and connectivity if unsure. - Diameter by double BFS with negative weights. It returns wrong answers; use the DP.
Variations
- Dominating set / Binary Tree Cameras. Three states per node: has a camera, covered by a child, not covered.
- Tree matching. Maximum set of edges with no shared endpoint (CSES Tree Matching): states " is matched to a child" / " is free".
- -coloring counts. "Colour the tree with colours, adjacent nodes different" has the closed form ; constraints like "some nodes pre-coloured" need a DP with one state per colour.
- Distance- independent set / covering within distance . State grows to "distance to the nearest chosen node", .
- Rerooting for farthest node. Keep the top two downward heights per node;
up[c] = 1 + max(up[p], best child height of p other than c). CSES Tree Distances I. - Small-to-large merging ("DSU on tree"). When each subtree carries a set or map (distinct colours in a subtree), merge the smaller structure into the larger: total. Related in spirit to the pair-counting proof above.
- Heavy-light and centroid decomposition. When queries ask about paths or the tree changes, see Heavy-Light & Centroid Decomposition.
- Tree DP on graphs of small treewidth. The same "small interface between independent pieces" idea solves NP-hard problems on tree-like graphs in .
- DP on DAGs. If a node can have several parents, it is a DAG, not a tree: see DAG DP.
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Diameter of Binary Tree (LeetCode 543) — Longest path, in edges, between any two nodes of a binary tree. Teaches "return height, track the bent path globally".
Hint
through = h(L) + h(R) + 2 with ; return , keep the max of through.
2. Subordinates (CSES 1674) — Given each employee's boss, output how many people are below each employee. Teaches subtree sizes over an iterative order.
Hint
size[v] - 1. The input gives parents for nodes 2..n, so a reversed BFS order (or reverse index order if bosses always have smaller ids — check the statement, do not assume) works.
3. House Robber III (LeetCode 337) — Rob houses arranged as a binary tree; two directly linked houses cannot both be robbed. Teaches the (take, skip) pair.
Solution
def rob(root):
def go(node): # returns (take, skip)
if node is None:
return (0, 0)
lt, ls = go(node.left)
rt, rs = go(node.right)
return (node.val + ls + rs, max(lt, ls) + max(rt, rs))
return max(go(root))
The tree has at most nodes, so a recursive solution may need more than Python's default 1,000 frames on a skewed tree; raise the limit or use the order array from this lesson.
4. Tree Diameter (CSES 1131) — Diameter of a general tree with up to nodes. Teaches top-two heights with arbitrary child counts and iterative order.
Hint
down1, down2 per node; answer max(down1 + down2). Or double BFS (edges are unweighted here).
5. Independent Set (AtCoder DP Contest P) — Count black/white paintings of a tree with no two adjacent blacks, modulo . Teaches the counting version of MIS.
Solution
MOD = 10**9 + 7
def count_paintings(n, edges):
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
parent, order, stack = [-1] * n, [], [0]
while stack:
v = stack.pop()
order.append(v)
for w in adj[v]:
if w != parent[v]:
parent[w] = v
stack.append(w)
white, black = [1] * n, [1] * n
for v in reversed(order):
p = parent[v]
if p != -1:
white[p] = white[p] * (white[v] + black[v]) % MOD
black[p] = black[p] * white[v] % MOD
return (white[0] + black[0]) % MOD
assert count_paintings(3, [(0, 1), (1, 2)]) == 5
assert count_paintings(1, []) == 2
6. Tree Matching (CSES 1130) — Maximum number of edges, no two sharing a node. Teaches "is already used by a child?" states.
Hint
free[v] = best with unmatched = ; used[v] = best with matched to one child = , maximised over . (A greedy "match leaves to parents bottom-up" also works.)
7. Binary Tree Maximum Path Sum (LeetCode 124) — Largest sum along any path; values can be negative. Teaches extendable vs. bent values, initialisation.
Hint
See Tree Problem Patterns. gain(v) = val + max(0, gain(L), gain(R)).
8. Binary Tree Cameras (LeetCode 968) — Fewest cameras so every node is watched by itself or a neighbour. Teaches three-state dominating set.
Solution
States per node: has (camera here), covered (no camera, watched by a child), needs (no camera, not watched). For null: has = ∞, covered = 0, needs = ∞ — a missing child never needs cover and can never cover.
INF = float("inf")
def min_camera_cover(root):
def go(node): # returns (has, covered, needs)
if node is None:
return (INF, 0, INF)
lh, lc, ln = go(node.left)
rh, rc, rn = go(node.right)
has = 1 + min(lh, lc, ln) + min(rh, rc, rn)
covered = min(lh + min(rh, rc), rh + min(lh, lc))
needs = lc + rc
return (has, covered, needs)
h, c, _ = go(root)
return min(h, c)
The root cannot be in needs (nobody above it), so the answer is min(has, covered). A known greedy (place cameras at parents of uncovered leaves, bottom-up) gives the same answer.
9. Tree Distances II (CSES 1133) — For every node, the sum of distances to all nodes. Teaches the rerooting formula; same as LeetCode 834 Sum of Distances in Tree.
Hint
The code in this lesson is a full solution: D(c) = D(p) + n - 2*size[c].
10. Tree Distances I (CSES 1132) — For every node, the distance to the farthest node. Teaches rerooting with a non-invertible max.
Solution
Top-two downward heights and an upward value; or the generic reroot with identity=0, merge=max, lift=x+1, finalize=acc.
def farthest(n, edges):
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
parent, order, stack = [-1] * n, [], [0]
while stack:
v = stack.pop()
order.append(v)
for w in adj[v]:
if w != parent[v]:
parent[w] = v
stack.append(w)
d1, d2, via = [0] * n, [0] * n, [-1] * n # top two heights, child giving d1
for v in reversed(order):
p = parent[v]
if p != -1:
h = d1[v] + 1
if h > d1[p]:
d2[p], d1[p], via[p] = d1[p], h, v
elif h > d2[p]:
d2[p] = h
up = [0] * n
for v in order:
p = parent[v]
if p != -1:
other = d2[p] if via[p] == v else d1[p]
up[v] = 1 + max(up[p], other)
return [max(d1[v], up[v]) for v in range(n)]
assert farthest(7, [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (4, 6)]) == [3, 3, 4, 4, 4, 5, 5]
11. Minimum Height Trees (LeetCode 310) — Find all roots giving minimum height. Teaches that the answer is the tree's centre(s), via rerooting or leaf-peeling.
Hint
Run Tree Distances I and keep the nodes with the minimum value; or repeatedly strip leaves until at most 2 nodes remain.
12. Maximum White Subtree (Codeforces 1324F) — For each node, the best (white − black) count over connected subgraphs containing it. Teaches rerooting with max(0, child) contributions.
Hint
down[v] = val[v] + Σ max(0, down[c]) with val = +1/−1. Reroot: ans[c] = down[c] + max(0, ans[p] - max(0, down[c])). Subtraction is fine here because the merge is +.
13. Tree with Maximum Cost (Codeforces 1092F) — Weighted sum of distances; choose the best root. Teaches the weighted rerooting formula.
Hint
Replace sizes with weight sums : D(c) = D(p) + W_total - 2*W_sub[c].
14. Subtree (AtCoder DP Contest V) — For each node, count connected black sets containing it, modulo an arbitrary . Teaches the prefix/suffix rerooting template (no inverses).
Hint
The generic reroot with identity=1, merge=product mod M, lift=x+1, finalize=acc is a full solution. The lesson's example uses .
15. Karen and Supermarket (Codeforces 815C) — Buy goods within a budget; a coupon may be used only if the coupon it depends on is used. Teaches tree knapsack where the "items" are costs and the states also track "coupon chain active".
Hint
dp[v][j][0/1] = min cost to buy items in , with / without 's coupon used. Merge children with the size-bounded loops for . Answer: largest with cost budget.
Common mistakes & interview follow-ups
"Your recursion will overflow on a path of nodes. Fix it." Show the order-array conversion: one iterative DFS for order and parent, then loop it backwards. Mention that BFS order works equally well.
"Can you return the set, not just the value?" Walk down in pre-order using the stored pairs and the same tie-break. No extra DP is needed.
"Now answer it for every root." Recognise rerooting. Write the up pass, then derive how the answer changes when the root moves across one edge. If the merge is max or a modular product with a composite modulus, use prefix/suffix (or top-two for max).
"Why is tree knapsack and not ?" The pair-counting argument: each merge's cost is the number of pairs of nodes whose LCA is the current node, split across the two sides being merged; every pair is counted once. Then point out the loop-limit condition.
"Is MIS easy on general graphs too?" No. It is NP-hard; the tree DP relies on "no edges between different child subtrees". For graphs of small treewidth, a generalised DP works.
"What changes for a forest?" Run the DP from every unvisited node and combine (sum for MIS, max for diameter).
Mistakes interviewers watch for: recursion on deep trees; assuming a binary tree when the input is a general tree; integer overflow on distance sums; subtracting under max; knapsack loops; forgetting the tree.
Quick quiz
1. In the MIS trace, node 1 reports (take, skip) = (8, 10). Which nodes form the "skip" value 10?
Answer
3 and 6 (4 + 6). Node 1 is not chosen, node 3 is taken (4 > 0), node 4 is skipped in favour of its child 6 (6 > 1).
2. What is the minimum vertex cover size of a star with 1 centre and 9 leaves, and what do in/out at the centre equal?
Answer
1 (the centre). in = 1 + 9·min(1, 0) = 1; out = 9·1 = 9.
3. Sum of distances: and size[1] = 4 in a 7-node tree. What is ?
Answer
.
4. Why can't you compute the "farthest node from every node" by subtracting the child's contribution, like sum of distances?
Answer
The merge is max. Knowing the maximum of a set and one removed element does not tell you the maximum of the rest. Use prefix/suffix maxima or keep the top two values.
5. You write tree knapsack with both loops running to at every merge, and . What is the running time?
Answer
: merges, each. Bounding loops by current sizes gives .
6. Which traversal orders can drive the up pass?
Answer
Any order in which every child comes before its parent: reversed DFS pre-order, reversed BFS order, or a true post-order.
Further reading / sources
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS) — the dynamic programming chapter (Chapter 15 in the 3rd edition, 14 in the 4th) and its end-of-chapter problem "Planning a company party" (Problem 15-6 in the 3rd edition), which is the MIS-on-a-tree party problem.
- Jon Kleinberg and Éva Tardos, Algorithm Design (2005) — §10.2 "Solving NP-hard problems on trees" (maximum-weight independent set on trees) and §10.4–10.5 (tree decompositions, treewidth).
- Steven Skiena, The Algorithm Design Manual, 3rd ed. (2020) — vertex cover and independent set catalogue entries, including the tree case.
- Antti Laaksonen, Competitive Programmer's Handbook — Chapter 14 "Tree algorithms" (subtree DP, diameter, all longest paths) and Chapter 18 (binary lifting); also the CSES problem set's tree section.
- cp-algorithms, Lowest Common Ancestor — Binary Lifting.
- Codeforces community tutorials on tree knapsack and on rerooting — the / tree knapsack bound and the prefix/suffix rerooting template are competitive-programming folklore documented in those blog posts rather than in a single paper.
- AtCoder Educational DP Contest, problem list — P (Independent Set) and V (Subtree).
- Judea Pearl, "Reverend Bayes on inference engines: a distributed hierarchical approach", AAAI 1982 (message passing on trees).
- Joseph Felsenstein, "Evolutionary trees from DNA sequences: a maximum likelihood approach", Journal of Molecular Evolution 17, 1981.
- Alfred V. Aho, Mahadevan Ganapathi, Steven W. K. Tjiang, "Code generation using tree matching and dynamic programming", ACM TOPLAS 11(4), 1989.
- Bruno Courcelle, "The monadic second-order logic of graphs I: Recognizable sets of finite graphs", Information and Computation 85(1), 1990.
Lessons: previous — Partition DP · next — DAG DP · module — Dynamic Programming · course — DSA: Zero to Mastery.
Related Archon pages: Tree Problem Patterns · Binary Trees & Traversals · LCA & Binary Lifting · Heavy-Light & Centroid Decomposition · DFS · Recursion & Induction · Grid DP · 0/1 Knapsack.