# DP on Trees - Introduction

Authors: Michael Cao, Benjamin Qi

Using subtrees as subproblems.

Focus Problem – read through this problem before continuing!

## Tutorial

Resources | ||||
---|---|---|---|---|

CF | ||||

Philippines | bad code format |

### Pro Tip

Don't just dive into trying to figure out a DP state and transitions -- make some observations if you don't see any obvious DP solution! Also, sometimes a greedy strategy suffices in place of DP.

## Solution - Tree Matching

### Solution 1

In this problem, we're asked to find the maximum matching of a tree, or the largest set of edges such that no two edges share an endpoint. Let's use DP on trees to do this.

Root the tree at node $1$, allowing us to define the subtree of each node.

Let $dp_2[v]$ represent the maximum matching of the subtree of $v$ such that we don't take any edges leading to some child of $v$. Similarly, let $dp_1[v]$ represent the maximum matching of the subtree of $v$ such that we take one edge leading into a child of $v$. Note that we can't take more than one edge leading to a child, because then two edges would share an endpoint.

#### Taking No Edges

Since we will take no edges to a child of $v$, the children vertices of $v$ can all take an edge to some child, or not. Additionally, observe that the children of $v$ taking an edge to a child will not prevent other children of $v$ from doing the same. In other words, all of the children are independent. So, the transitions are:

#### Taking One Edge

The case where we take one child edge of $v$ is a bit trickier. Let's assume the edge we take is $v \rightarrow u$, where $u \in child(v)$. Then, to calculate $dp_1[v]$ for the fixed $u$:

In other words, we take the edge $v \rightarrow u$, but we can't take any children of $u$ in the matching, so we add $dp_2[u] + 1$. Then, to deal with the other children, we add:

Fortunately, since we've calculated $dp_2[v]$ already, this expression simplifies to:

Overall, to calculate the transitions for $dp_1[v]$ over all possible children $u$:

### Warning!

Loop through the children of $v$ twice to calculate $dp_1[v]$ and $dp_2[v]$ separately! You need to know $dp_2[v]$ to calculate $dp_1[v]$.

Code

### Solution 2 - Greedy

Just keep matching a leaf with the only vertex adjacent to it while possible.

Code

## Problems

### Easier

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

AC | Easy | ## Show TagsDP, Tree | |||

Gold | Easy | ## Show TagsDP, Tree | |||

CF | Normal | ## Show TagsDP, Tree | |||

Baltic OI | Normal | ## Show TagsGreedy, Tree | |||

CF | Normal | ## Show TagsGreedy, Tree | |||

POI | Normal | ## Show TagsTree | |||

CF | Normal | ## Show TagsDP, Tree | |||

Gold | Hard | ## Show TagsGreedy, Tree | |||

POI | Hard | ## Show TagsFunctional Graph | |||

POI | Hard | ## Show TagsFunctional Graph |

### Warning!

Memory limit for "Spies" is very tight.

### Harder

These problems are not Gold level. You may wish to return to these once you're in Platinum.

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

COI | Very Hard | ## Show TagsDP, Tree | |||

Plat | Very Hard | ## Show TagsBinary Search, DP, Tree | |||

CF | Very Hard | ## Show TagsDP, Tree | |||

IOI | Insane | ## Show TagsDP, Tree | |||

CSES | Insane | ## Show TagsGreedy, Tree | |||

Baltic OI | Insane | ## Show TagsDP, Tree |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!