Dynamic Programming on Subtrees (DP on Subtree)

Dynamic Programming on Subtrees (DP on Subtree)

Introduction

A tree has no cycles, but its edges are initially undirected. To use dynamic programming, we choose any vertex as the root. This gives every other vertex one parent and divides the tree into subtrees.

Subtree DP calculates the answer for a vertex from the answers of its children. The DFS enters a vertex, solves every child subtree, and only then combines those results. In other words, the recursion itself provides the required bottom-up order.

This technique appears in problems about choosing vertices, matching edges, counting configurations, collecting values, and optimizing decisions under parent-child restrictions. By the end of this lecture, we will know how to choose subtree states, combine independent child subtrees, and implement the transitions with a postorder DFS.

Problem or motivation

We will use the maximum-weight independent set on a tree.

Each vertex $v$ has a positive weight $\operatorname{weight}[v]$. We want to choose some vertices with maximum total weight, but two vertices joined by an edge cannot both be chosen.

For a general graph, this problem is difficult because decisions can interact through many cycles. A tree is different. Once we decide whether a vertex is chosen, its child subtrees no longer interact with each other. That separation is exactly what subtree DP uses.

Naive approach

We could enumerate every subset of vertices, reject subsets containing both endpoints of an edge, and keep the largest valid sum.

There are $2^n$ subsets. Even though checking one subset is straightforward, this approach becomes impossible very quickly.