Not Frequent
0/19

# DP on Trees - Introduction

Authors: Michael Cao, Benjamin Qi

Using subtrees as subproblems.

### Prerequisites

Focus Problem – try your best to solve this problem before continuing!

## Tutorial

Resources
CF
Philippines

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

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

$dp_1[v] = dp_2[u] + 1 + dp_2[v] - \max(dp_2[u], dp_1[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:

$\sum_{w \in child(v), w \neq u} \max(dp_1[w], dp_2[w]).$

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

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

Overall, to calculate the transitions for $dp_1[v]$ over all possible children $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 $v$ twice to calculate $dp_1[v]$ and $dp_2[v]$ separately! You need to know $dp_2[v]$ to calculate $dp_1[v]$.

C++

#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

Java

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.

C++

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++;

Java

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

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

### 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!