PrevNext
Not Frequent
 0/16

DP on Trees - Introduction

Authors: Michael Cao, Benjamin Qi

Using subtrees as subproblems.

Focus Problem – read through this problem before continuing!

Tutorial

Resources
CF
Philippinesbad 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),wudp2[w].\sum_{w \in child(v), w \neq u} 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 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

Module Progress:

Give Us Feedback on DP on Trees - Introduction!

PrevNext