Not Frequent
0/16

# DP on Trees - Introduction

Authors: Michael Cao, Benjamin Qi

### Prerequisites

Using subtrees as subproblems.

Focus Problem – read through this problem before continuing!

## Tutorial

Resources
CF

### 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:

$dp_2[v] = \sum_{u \in child(v)} max(dp_1[u], dp_2[u])$

#### 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$:

$dp_1[v] = dp_2[u] + 1 + dp_2[v] - max(dp_2[u], dp_1[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:

$\sum_{w \in child(v), w \neq u} dp_2[w].$

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

$dp_2[v] - \max(dp_2[u], dp_1[u])$

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

$dp_1[v] = \max_{u \in child(v)} (dp_2[u] + 1 + dp_2[v] - \max(dp_2[u], dp_1[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

StatusSourceProblem NameDifficultyTagsSolution
ACEasy
Show Tags

Tree, DP

GoldEasy
Show Tags

Tree, DP

External Sol
CFNormal
Show Tags

Tree, Greedy

Check CF
POINormal
Show Tags

Tree, DP

View Solution
POINormal
Show Tags

Binary Search

View Solution
POINormalView Solution
GoldHard
Show Tags

Greedy

External Sol
POIHard
Show Tags

Func Graph

POIHard
Show Tags

Func 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.

StatusSourceProblem NameDifficultyTagsSolution
COIVery Hard
Show Tags

DP, Tree

PlatVery Hard
Show Tags

DP, Tree, Binary Search

External Sol
CFVery Hard
Show Tags

DP, Tree

Check CF
IOIInsane
Show Tags

DP, Tree

External Sol
CSESInsane
Show Tags

Tree, Greedy

Show Sketch
Baltic OIInsane
Show Tags

Tree, DP