Not Frequent

DP on Trees - Introduction

Authors: Michael Cao, Benjamin Qi

Using subtrees as subproblems.

Focus Problem – read through this problem before continuing!



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]))


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


Solution 2 - Greedy

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




StatusSourceProblem NameDifficultyTags
Show TagsDP, Tree
Show TagsDP, Tree
Baltic OINormal
Show TagsGreedy, Tree
Show TagsGreedy
Show TagsFunctional Graph
Show TagsFunctional Graph


Memory limit for "Spies" is very tight.


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
Show TagsDP, Tree
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!