Tree DP
Tree DP is dynamic programming on a rooted tree. The subtree of a vertex is together with everything below it: its children, their children, and so on down to the leaves. Each state describes one subtree, and the transition builds a subtree’s answer from the answers for its root’s children, whose subtrees are smaller. House Robber III is a first example.
Houses form a binary tree, and each node holds some money. A thief may rob any set of houses, except that robbing two houses joined directly by an edge sets off the alarm. You get the root of the tree. Return the most money the thief can take without setting off the alarm.
Constraints
- The tree has between and nodes
-
Node.val
Sample 1 · Input
root = [3,2,3,null,3,null,1]
Output
7
Sample 2 · Input
root = [3,4,5,1,3,null,1]
Output
9
In the first sample, the root 3 has a left child 2 and a right child 3; the 2 has a right child 3, and the right-hand 3 has a right child 1. Robbing the root and the two grandchildren gives . In the second, the root 3 has children 4 and 5, and robbing those two gives , more than any set that includes the root.
A natural first attempt keeps one number per subtree: let best(v) be the most money in ’s subtree, and build it from best of the two children. In the second sample, best(4) = 4 and best(5) = 5. If the thief robs the root, neither child may be robbed, so the root needs the best of each child’s subtree without that child. But the number 5 does not say whether house 5 was robbed, and the best without house 5 is only 1. The root could find that 1 by reaching past its children to the subtrees of its grandchildren. That works, but it makes every node look two levels down. A simpler fix is to have every subtree report two numbers instead of one.
Return both states from every subtree
The parent needs to know whether each child was robbed, so every subtree reports one answer for each case: take, the most money with its root robbed, and skip, the most with its root left alone. If we rob a node, neither child may be robbed, so both children must be in their skipped state. If we leave it alone, the houses robbed in its subtree are just the houses robbed in its two child subtrees. No edge joins those two subtrees, so a choice in one never restricts the other, and each child may use whichever of its states is larger. An empty subtree reports :
Here and are the left and right children. The root has no parent to restrict it, so the answer is the larger of its two numbers.
A node needs both children’s pairs first, so the pairs are computed from the leaves up. Any order that puts every node after its children will do, and a recursive function gives one: it returns from both children before it combines them. That order is called a postorder. No memo is needed, because each node is reached by exactly one call, from its parent, and that call hands the pair straight back up.
In the problems that follow, the parent needs some fact about each child’s root, here whether it was robbed, and each subtree returns one answer for each value that fact can take. We call that fact the boundary condition, because it describes the child’s root, the vertex where the child’s subtree meets its parent. Each problem below answers the same three questions.
Return the pair from a recursive call
best(node) returns the pair for node’s subtree, and rob keeps the larger number at the root. The calls at the bottom build the two samples.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def rob(root):
def best(node): # returns (take, skip) for node's subtree
if node is None:
return 0, 0
left_take, left_skip = best(node.left)
right_take, right_skip = best(node.right)
take = node.val + left_skip + right_skip
skip = max(left_take, left_skip) + max(right_take, right_skip)
return take, skip
return max(best(root))
# the samples [3,2,3,null,3,null,1] and [3,4,5,1,3,null,1]
print(rob(TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))))
print(rob(TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(3)), TreeNode(5, None, TreeNode(1)))))Prints 7, then 9.
Python details
A chain of 10,000 nodes needs 10,000 nested calls, past Python’s default limit of 1,000: raise it with sys.setrecursionlimit.
Let’s trace the first sample. The leaves 3 and 1 return and . The left child 2 returns , and the right child 3 returns . The root then has two choices:
so it keeps 7. On the second sample, house 4 returns and house 5 returns , so the root takes or skips for , and keeps 9.
Subtree-state invariant
Once a node is processed, take and skip hold the exact optimum for its whole subtree, take with that node robbed and skip with it left alone.
The proof is by induction from the leaves up, and it begins at the empty subtree, where both values are 0 and exact. Now suppose they are exact for both children. If the node is robbed, each child must be skipped, and joining the best skipped answers is allowed because no edge joins the two child subtrees. If the node is skipped, its edges to the children cannot join two robbed houses, so each child may use either state, and the larger one is best. Nothing does better than these sums either: any allowed choice of houses in the subtree, cut down to one child’s subtree, is an allowed choice there in the state that matches that child, so that part is worth at most the child’s value. So the invariant holds at every node.
Largest independent set: the same states in any tree
The two states do not depend on the tree being binary. If every house holds 1, House Robber III asks for the largest independent set of the tree: a set of vertices with no edge between any two of them. In an arbitrary graph no one knows a fast way to find the largest independent set, but in a tree the two states find it in time. A vertex of a general tree can have any number of children, so the two sums run over all of them. Over the children of :
Let’s compute it for the tree with parents [-1, 0, 0, 1, 1]: entry is the parent of vertex , so vertex 0 is the root, 1 and 2 are its children, and 3 and 4 are children of 1. A leaf has take 1 and skip 0. Vertex 1 has the leaves 3 and 4 as children, so and . Vertex 2 is a leaf. At the root,
so the answer is 3: either or .
Step through the subtree returns
The widget steps through the take and skip calculation on the same tree. If you change the root, the order and the pairs in the middle change, but the answer at the root stays 3.
Worked example
Trace both independent-set states
The first preset is the same tree, and the other three are new. On Star with four leaves, skipping the center allows all four leaves, while selecting it allows only the center itself. On Path of five vertices the best set takes every other vertex, and Single edge is the smallest tree where the root’s choice restricts its child.
Root the tree at vertex 0. Each vertex returns two values: the best independent set with it selected and the best with it skipped.
- parents
- -1, 0, 0, 1, 1
Change the example input
Current result: 3
Maximum matching: a different boundary condition
So far, the parent has needed to know whether each child was selected. Our next problem needs a different fact about each child: whether it is still free.
You get a tree with nodes, numbered to . A matching is a set of edges in which every node is an endpoint of at most one edge. Print the largest number of edges in a matching.
The first line holds , and each of the next lines holds an edge .
Constraints
Sample · Input
5 1 2 1 3 3 4 3 5
Output
2
Let’s read the sample. Node 1 is joined to nodes 2 and 3, and node 3 to nodes 4 and 5. The edges (1, 2) and (3, 4) form a matching of size 2, and any third edge would touch node 1 or node 3 again.
A vertex can be matched to at most one neighbour, so the boundary condition is whether the vertex is already matched to one of its own children. Let unmatched[v] be the largest matching in ’s subtree that leaves free for its parent, and matched[v] the largest one that pairs with a child.
If stays free, each child contributes its better state on its own. If is matched, exactly one child is its partner: that child must be free, the edge adds 1, and every other child still contributes its better state. Writing and for the two arrays and :
The term inside the maximum is how much the total changes when becomes the partner. The edge adds 1, and must now stay free, so its subtree contributes instead of its better value . A leaf has no child to match, so its matched value does not exist. Storing -1 works, because the maximum with unmatched[leaf] = 0 then ignores it.
Let’s check this on the sample. We number its vertices from 0, so the sample’s node 1 becomes vertex 0, node 2 becomes vertex 1, and so on. We root the tree at vertex 0: the root has children 1 and 2, and vertex 2 has the leaves 3 and 4. The leaves 1, 3 and 4 give and . Vertex 2 gets and by pairing with leaf 3.
At the root, . To choose its partner, compare the two gains:
Vertex 2 would give up its own edge, so leaf 1 is the better partner, and : the edges and , which are and in the sample’s numbering.
Root the edge list, then walk it backwards
CSES gives the tree as undirected edges with no root, so the program picks vertex 0 as the root. Any vertex would do: which vertex is drawn at the top changes the parents and children, but not which sets of edges are matchings. A breadth-first pass from the root lists the vertices with every parent before its children, and records as each vertex’s parent the vertex it was reached from. In a tree, the only neighbour of already listed when is read is its parent, so the test u != parent[v] replaces the visited array that a breadth-first search needs on a general graph. Reading that list backwards finishes every child before its parent, with no recursion at all.
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
graph = [[] for _ in range(n)]
for i in range(n - 1):
a, b = int(data[2 * i + 1]) - 1, int(data[2 * i + 2]) - 1
graph[a].append(b)
graph[b].append(a)
parent = [-1] * n
order = [0]
for v in order: # order grows while the loop reads it: a BFS
for u in graph[v]:
if u != parent[v]:
parent[u] = v
order.append(u)
unmatched = [0] * n # v is not matched to a child
matched = [-1] * n # v is matched to one child; -1 while v has none
for v in reversed(order): # children before parents
children = [c for c in graph[v] if c != parent[v]]
for c in children:
unmatched[v] += max(unmatched[c], matched[c])
for c in children:
gain = unmatched[c] + 1 - max(unmatched[c], matched[c])
matched[v] = max(matched[v], unmatched[v] + gain)
print(max(unmatched[0], matched[0]))
main()On the sample input, the program prints 2.
The children are read twice because the second loop needs the finished unmatched[v]. The work at one vertex grows with its number of children, which varies a lot: the center of a star has . So count the work from the child’s side instead. Each vertex is read as a child only by its parent, a constant number of times, and the adjacency lists hold entries in all, so the whole program is .
Counting colorings with products
Every problem above asked for a maximum, and the same two states can also count.
You get a tree with vertices, numbered to . Paint each vertex white or black so that no two adjacent vertices are both black. Print the number of ways, modulo .
The first line holds , and each of the next lines holds an edge .
Constraints
- The graph is a tree
Sample 1 · Input
3 1 2 2 3
Output
5
Sample 2 · Input
4 1 2 1 3 1 4
Output
9
Sample 3 · Input
1
Output
2
The first sample is the path 1, 2, 3, and its five colorings are WWW, BWW, WBW, WWB and BWB. As in the independent set, the boundary condition is the color of the root, but now we count colorings instead of maximizing.
When we count, the answers of different children are multiplied instead of added, because once ’s color is fixed, the colorings of different child subtrees are chosen independently, and independent choices multiply: if one child allows 3 colorings and another allows 2, together they allow . The two states of a single child are alternatives, so they are added. A white vertex allows either color below it, and a black one only white children:
Here and count the colorings of ’s subtree with white and with black; the program stores them in the arrays white and black. A leaf has , and the answer is . Let’s run it on the path. The end vertex 3 has , and then
so there are colorings.
On the second sample, vertex 1 has three leaves, so and , and there are 9. For parents [-1, 0, 0, 1, 1] the same rule gives colorings, one for each independent set of that tree, the empty one included, because the black vertices of an allowed coloring are exactly an independent set.
Deeper read: the full Independent Set program
The program roots the edge list exactly as the Tree Matching program does and then runs the two products.
MOD = 10**9 + 7
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
graph = [[] for _ in range(n)]
for i in range(n - 1):
a, b = int(data[2 * i + 1]) - 1, int(data[2 * i + 2]) - 1
graph[a].append(b)
graph[b].append(a)
parent = [-1] * n
order = [0]
for v in order:
for u in graph[v]:
if u != parent[v]:
parent[u] = v
order.append(u)
white = [1] * n # colorings of v's subtree with v white
black = [1] * n # colorings of v's subtree with v black
for v in reversed(order):
for c in graph[v]:
if c != parent[v]:
white[v] = white[v] * (white[c] + black[c]) % MOD
black[v] = black[v] * white[c] % MOD
print((white[0] + black[0]) % MOD)
main()On the second sample, the program prints 9.
Three boundary states: watched from below or from above
Binary Tree Cameras needs a boundary condition with three values.
You get the root of a binary tree. A camera placed on a node watches that node, its parent and its children. Return the fewest cameras that watch every node.
Constraints
- The tree has between and nodes
Node.val
Sample 1 · Input
root = [0,0,null,0,0]
Output
1
Sample 2 · Input
root = [0,0,null,0,null,0,null,null,0]
Output
2
In the first sample, the root has one child, which has two children, and one camera on that child watches all four nodes. In the second, the five nodes form a chain, and two cameras are needed.
A node without a camera can be in two different situations: a child’s camera watches it, or nothing below watches it yet. The second is allowed only if the parent then holds a camera, so the parent must be able to tell them apart. Each subtree therefore returns three values, each the fewest cameras that watch every node below its root:
If the root is uncovered, neither child holds a camera and each child must be watched from below. If it is covered, at least one child holds a camera, and a child without one must be covered. If it holds a camera, that camera watches both children, so each child may use any of its three states. For the left child and right child :
A missing child needs no watching and cannot hold a camera, so both of its camera-free states cost 0 and it returns . At the root no parent can help, so the answer is the smaller of and .
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
INF = float("inf")
def min_camera_cover(root):
def states(node): # returns (uncovered, covered, camera)
if node is None:
return 0, 0, INF
lu, lc, lk = states(node.left)
ru, rc, rk = states(node.right)
uncovered = lc + rc
covered = min(lk + min(rc, rk), rk + min(lc, lk))
camera = 1 + min(lu, lc, lk) + min(ru, rc, rk)
return uncovered, covered, camera
_, covered, camera = states(root)
return min(covered, camera)
# the samples [0,0,null,0,0] and [0,0,null,0,null,0,null,null,0]
print(min_camera_cover(TreeNode(0, TreeNode(0, TreeNode(0), TreeNode(0)))))
print(min_camera_cover(TreeNode(0, TreeNode(0, TreeNode(0, TreeNode(0, None, TreeNode(0)))))))Prints 1, then 2.
Let’s trace the first sample. Each leaf returns : it cannot be covered from below, and a camera on it costs 1. The middle node then gets
Without its own camera, the middle node needs one on a leaf, and then the other leaf needs its own too. The root has no right child, so its is the middle node’s camera count, 1, and its own camera would cost 2. The answer is 1.
Answer every vertex: rerooting
AtCoder’s Subtree asks for a separate answer for every vertex.
You get a tree with vertices and a number . Paint each vertex white or black so that the black vertices are connected: any black vertex can reach any other through black vertices only. For every vertex , print the number of such colorings in which is black, modulo .
The first line holds and , and each of the next lines holds an edge . Print lines.
Constraints
- The graph is a tree
Sample 1 · Input
3 100 1 2 2 3
Output
3 4 3
Sample 2 · Input
4 100 1 2 1 3 1 4
Output
8 5 5 5
The first sample is the path 1, 2, 3. With vertex 2 black there are four colorings: 2 alone, with 1, with 3, or with both. With vertex 1 black there are three: 1 alone, with 2, or with 2 and 3.
The direct method roots the tree at each vertex in turn and runs a tree DP from there. Each run costs , so with the runs take about
about 100 seconds at a rough steps a second. Rerooting shares the work between roots instead: it solves the problem for one root, then passes what each vertex needs down from its parent. We root the tree at vertex 0 and let down[v] count the colorings of ’s subtree with black and every black vertex in it connected to . For each child , either is white, and then its whole subtree is white, because a black vertex there would be cut off from ; or is black, and its subtree is colored in one of down[c] ways:
down[root] is the root’s answer. In the second sample each leaf has , so the center gets .
Every other vertex also needs the part of the tree outside its subtree. Let up[v] count the ways to color everything outside ’s subtree, with black, so that every black vertex out there connects to through ’s parent. The root has nothing outside, so , and the answer for any is , because once is black, the inside and the outside of its subtree are colored independently.
For a child of , either is white, and then everything outside ’s subtree must be white, one coloring; or is black, and the outside of ’s subtree contributes up[v] while each sibling of contributes :
For a leaf of the second sample, that is .
Leave one child out with prefix and suffix products
The product over the siblings is ’s full product with one factor left out. Multiplying the siblings again for each child is too slow: a vertex with children would make about multiplications, and the center of a star with vertices would make about . Dividing the full product by the left-out factor would need a modular inverse, a number whose product with the factor is 1 modulo . An inverse exists only when the factor and have no common divisor above 1, and here need not be prime: with , the factor 2 has no inverse, and a factor can even be 0 modulo .
Instead, we list ’s children in order and compute prefix and suffix products of their factors: prefix[i] multiplies the factors before child , and suffix[i + 1] those after it. The product without child is prefix[i] * suffix[i + 1], and both arrays take one pass over ’s children. For the factors 3, 2 and 5, prefix is [1, 3, 6, 30] and suffix is [30, 10, 5, 1], so leaving out the middle factor gives .
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
graph = [[] for _ in range(n)]
for i in range(n - 1):
a, b = int(data[2 * i + 2]) - 1, int(data[2 * i + 3]) - 1
graph[a].append(b)
graph[b].append(a)
parent = [-1] * n
order = [0]
for v in order:
for u in graph[v]:
if u != parent[v]:
parent[u] = v
order.append(u)
children = [[u for u in graph[v] if u != parent[v]] for v in range(n)]
down = [1] * n # v black, black part of v's subtree connected to v
for v in reversed(order): # children first
for c in children[v]:
down[v] = down[v] * (1 + down[c]) % m
up = [1] * n # v black, black part outside v's subtree connected to v
for v in order: # parents first
kids = children[v]
k = len(kids)
prefix = [1] * (k + 1)
for i in range(k):
prefix[i + 1] = prefix[i] * (1 + down[kids[i]]) % m
suffix = [1] * (k + 1)
for i in range(k - 1, -1, -1):
suffix[i] = suffix[i + 1] * (1 + down[kids[i]]) % m
for i in range(k):
up[kids[i]] = (1 + up[v] * prefix[i] % m * suffix[i + 1]) % m
print("\n".join(str(down[v] * up[v] % m) for v in range(n)))
main()On the second sample, the program prints 8, 5, 5 and 5.
The first pass runs children first, as before. The second runs parents first, because up[c] reads up[v], which must be final. Let’s check the first sample: down is [3, 2, 1] and up is [1, 2, 3], so the answers are , and : the middle vertex has two choices on each side.
Deeper read: merging whole tables from the children
Some tree problems need a table per vertex instead of a few numbers. Suppose each vertex has a weight and we must choose exactly vertices, including the root, so that each chosen vertex other than the root also has its parent chosen. Let best[v][j] be the largest total weight of chosen vertices in ’s subtree with among them.
We start with best[v] = [none, weight[v]], where none marks a count that cannot be reached (zero vertices cannot include ), and merge in the children one at a time. A child contributes either no vertices or vertices from its own table, so vertices chosen from and the children merged so far, plus from , give a candidate for vertices. Writing for best[v][j] and for the merged table, which starts as a copy of , each pair makes the update
def best_connected_set(parents, weight, k):
n = len(parents)
root = parents.index(-1)
children = [[] for _ in range(n)]
for v, p in enumerate(parents):
if p >= 0:
children[p].append(v)
order = [root]
for v in order:
order.extend(children[v])
NONE = float("-inf")
best = [None] * n # best[v][j]: j chosen vertices in v's subtree, v among them
for v in reversed(order):
cur = [NONE, weight[v]]
for c in children[v]:
child = best[c]
merged = cur + [NONE] * (len(child) - 1)
for a in range(1, len(cur)):
for b in range(1, len(child)):
merged[a + b] = max(merged[a + b], cur[a] + child[b])
cur = merged[:k + 1]
best[v] = cur
return best[root][k] if k < len(best[root]) else None
print(best_connected_set([-1, 0, 0, 1, 1], [2, 1, 3, 6, 1], 2))
print(best_connected_set([-1, 0, 0, 1, 1], [2, 1, 3, 6, 1], 3))Prints 5, then 9.
The table keeps every count instead of one answer, because the best vertices need not contain the best . On parents [-1, 0, 0, 1, 1] with weights [2, 1, 3, 6, 1], the best two vertices are with weight , but the best three are with weight : the light vertex 1 is worth taking because it allows taking vertex 3. Growing the best pair by one vertex would give at most 6.
If the tables are kept at full length, merging the tables of two parts with and vertices costs about steps, one for each pair of vertices taken one from each part. Each pair of vertices meets in a merge once, at the vertex where their paths to the root join, so all the merges together take . Cutting each table to entries, as the code does, lowers the total to ; OI Wiki’s tree DP page in Further reading states this bound and links a proof.
Tree DP time and space
- Fixed-size states
- Each child is read a constant number of times: about reads for Tree Matching’s nodes.
- Rerooting
- One pass over each vertex’s children, and all the children add up to .
- Rooting an edge list
- One breadth-first pass over edges.
- Space
- A few values per vertex, plus the adjacency lists and the processing order.
- Merging child tables
time and space - With each table cut to entries.
Common mistakes
Return only the better state from each subtree.
- Where it breaks
- On the single edge between 0 and 1, the leaf returns 1 and the root adds 1 for itself, reporting
2with both endpoints selected; the answer is1. - The fix
- Return both states so the parent can enforce its own choice.
Skip every child whenever its parent is skipped.
- Where it breaks
- The star
[-1, 0, 0, 0, 0]gives1, although all four leaves can be selected. - The fix
- A skipped parent allows the better state from every child.
Walk the vertices in decreasing index for an arbitrary parent array.
- Where it breaks
- Parents
[-1, 2, 0]is the path 0, 2, 1. Vertex 2 hands its values to 0 before vertex 1 has been added to it, and the independent set comes out1instead of2. - The fix
- Compute an order from the root and walk it backwards, or use a postorder DFS.
Let a matched vertex pair with every child that gains.
- Where it breaks
- On the star with four leaves, matching the center with each leaf reports
4edges, but every edge touches the center, so the answer is1. - The fix
- Choose exactly one partner child: add the single largest gain, not every positive gain.
Divide by a child’s factor when rerooting a product modulo M.
- Where it breaks
- In Subtree’s second sample, and each leaf’s factor is 2, which has no inverse modulo 100: Python’s
pow(2, -1, 100)raisesValueError. - The fix
- Leave the factor out with prefix and suffix products over the children.
Recall Why does Binary Tree Cameras need three states when the independent set needs two?
In the independent set, the only fact about a child that can conflict with the parent’s choice is whether the child is selected. In Binary Tree Cameras, a node without a camera is either already watched by a child or still waiting for its parent, and the second is allowed only under a parent with a camera. Merging them into one state would either reject layouts where the parent watches the child or accept trees with an unwatched node.
Recall Why does the rerooting program fill `down` from the leaves up but `up` from the root down?
down[v] reads down of its children, so the children must be finished first. up[c] reads its parent’s up and its siblings’ down, so the parent must be finished first; every down is known from the first pass.
Further reading
- USACO Guide, GoldDP on Trees - Introduction(opens in a new tab)
Solves Tree Matching with the same two states as this lesson and again greedily, then lists Independent Set and other tree DP practice.
- USACO Guide, GoldDP on Trees - Solving For All Roots(opens in a new tab)
Rerooting on Tree Distances I, with one array for the subtree and one for everything outside it, the
downandupsplit used for Subtree. - Antti Laaksonen (PDF)Competitive Programmer’s Handbook, Chapter 14: Tree algorithms(opens in a new tab)
Section 14.3, page 137, finds the longest path from every vertex in two passes, one down from the root and one back up, the same shape as the rerooting here.
- OI Wiki, in Chinese树形 DP (Tree DP)(opens in a new tab)
The take-or-skip party problem, tree knapsack over course prerequisites in , close to the deeper read here, and rerooting in two passes; its exercises include Subtree.
- Jeff Erickson (PDF)Algorithms, Chapter 3: Dynamic programming(opens in a new tab)
Section 3.10 finds the largest independent set of a tree, first with one value per vertex that looks down to the grandchildren and then with the two values used here, and counts the work from each vertex’s parent to show it is . Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.
