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.

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.

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.

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.