Tree DP

Tree DP computes dynamic programming values over a tree by combining results from child subtrees.

It works well because a subtree is a smaller problem with the same structure as the whole tree.

Core Idea

Choose a root, define what each node’s state means, compute child states first, and combine them at the parent.

Depth-first traversal is the usual computation order because it naturally finishes children before returning to the parent.

Function Contract

subtree_sizes(tree, root) expects an undirected tree represented as an adjacency list and a root vertex.

It returns a dictionary where size[node] is the number of nodes in the subtree rooted at node after the chosen root gives the tree parent-child direction.

Python Example

def subtree_sizes(tree, root):
    size = {}
 
    def dfs(node, parent):
        total = 1
        for neighbor in tree[node]:
            if neighbor != parent:
                total += dfs(neighbor, node)
        size[node] = total
        return total
 
    dfs(root, None)
    return size

Each node’s value depends on the values of its child subtrees.

State Design

A tree DP state usually means “the answer for the subtree rooted at this node.” Sometimes each node needs multiple states, such as:

dp[node][0] = best answer in this subtree when node is not chosen
dp[node][1] = best answer in this subtree when node is chosen

Multiple states are needed when the parent’s choice affects what children are allowed to do.

Why Postorder Matters

Parents often need child results. DFS postorder computes children before the parent, so the needed values are ready when the parent combines them.

Complexity

If each node combines child answers in time proportional to its number of children, the total time is O(n) for n nodes. The recursion stack is O(h), where h is tree height.

Common Confusions

An undirected tree often needs an explicit parent parameter so recursion does not walk back up and loop forever.

The root may be chosen by the algorithm even if the original tree was not given as rooted.

Another common mistake is assuming a child subtree is independent when the parent choice imposes a condition. That condition must be represented in the state.

When To Use It

Use tree DP when a problem asks for the best, count, size, or feasibility value for every subtree or for choices involving parent-child relationships.

Do not use simple tree DP if the graph can contain cycles unless the problem has been transformed into a tree structure.

The Main Point

Tree DP works because child subtrees can be solved before the parent combines their answers.