DP on Trees - Introduction

Tutorial

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 $d{p}_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 $d{p}_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\to u$, where $u\in child(v)$. Then, to calculate $d{p}_1[v]$ for the fixed $u$:

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

Fortunately, since we've calculated $d{p}_2[v]$ already, this expression simplifies to:

Overall, to calculate the transitions for $d{p}_1[v]$ over all possible children $u$:

Solution 2 - Greedy

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

Problems

Easier

Harder

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