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

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

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:

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

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

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int, int>;
#define f first

Copy
import java.io.*;
import java.util.*;

public class TreeMatching {
	static ArrayList<Integer> adj[];
	static int dp[][];
	static void dfs(int v, int p) {
		for (int to : adj[v]) {
			if (to != p) {
				dfs(to, v);

Solution 2 - Greedy

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

Copy
int n;
vi adj[MX];
bool done[MX];
int ans = 0;

void dfs(int pre, int cur) {
	for (int i : adj[cur]) {
		if (i != pre) {
			dfs(cur, i);
			if (!done[i] && !done[cur]) done[cur] = done[i] = 1, ans++;

Copy
import java.io.*;
import java.util.*;

public class TreeMatching {
	static ArrayList<Integer> adj[];
	static int N;
	static boolean done[];
	static int ans = 0;
	static void dfs(int v, int p) {
		for (int to : adj[v]) {

Problems

Easier

Harder

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