PrevNext
Not Frequent
 0/17

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 11, allowing us to define the subtree of each node.

Let dp2[v]dp_2[v] represent the maximum matching of the subtree of vv such that we don't take any edges leading to some child of vv. Similarly, let dp1[v]dp_1[v] represent the maximum matching of the subtree of vv such that we take one edge leading into a child of vv. 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 vv, the children vertices of vv can all take an edge to some child, or not. Additionally, observe that the children of vv taking an edge to a child will not prevent other children of vv from doing the same. In other words, all of the children are independent. So, the transitions are:

dp2[v]=uchild(v)max(dp1[u],dp2[u])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 vv is a bit trickier. Let's assume the edge we take is vuv \rightarrow u, where uchild(v)u \in child(v). Then, to calculate dp1[v]dp_1[v] for the fixed uu:

dp1[v]=dp2[u]+1+dp2[v]max(dp2[u],dp1[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 vuv \rightarrow u, but we can't take any children of uu in the matching, so we add dp2[u]+1dp_2[u] + 1. Then, to deal with the other children, we add:

wchild(v),wumax(dp1[w],dp2[w]).\sum_{w \in child(v), w \neq u} \max(dp_1[w], dp_2[w]).

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

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

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

dp1[v]=maxuchild(v)(dp2[u]+1+dp2[v]max(dp2[u],dp1[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 vv twice to calculate dp1[v]dp_1[v] and dp2[v]dp_2[v] separately! You need to know dp2[v]dp_2[v] to calculate dp1[v]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 NameDifficultyTags
ACEasy
Show TagsDP, Tree
GoldEasy
Show TagsDP, Tree
CFNormal
Show TagsDP, Tree
Baltic OINormal
Show TagsGreedy, Tree
CFNormal
Show TagsGreedy, Tree
POINormal
Show TagsTree
CFNormal
Show TagsDP, Tree
GoldHard
Show TagsGreedy, Tree
POIHard
Show TagsFunctional Graph
POIHard
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.

StatusSourceProblem NameDifficultyTags
COIVery Hard
Show TagsDP, Tree
PlatVery Hard
Show TagsBinary Search, DP, Tree
CFVery Hard
Show TagsDP, Tree
IOIInsane
Show TagsDP, Tree
CSESInsane
Show TagsGreedy, Tree
Baltic OIInsane
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!

PrevNext