CSES Solutions – Tree Matching
You are given a tree consisting of n nodes. A matching is a set of edges where each node is an endpoint of at most one edge. What is the maximum number of edges in a matching ?
Examples:
Input : N = 10 , edges = {{5,8}, {4,6}, {9,1}, {10,4}, {1,3}, {2,3}, {7,9}, {6,2}, {5,10}}
Output : 5
Explanation : One possible matching is {5-8 , 10-4, 1-3, 7-9 , 6-2}Input : N = 10 , edges = {{6,3}, {2,8}, {1,8}, {4,10}, {7,3}, {8,7}, {1,5}, {5,9}, {10,9}}
Output : 4
Explanation : one possible matching is {6-3, 2-8, 4-10, 1-5}
Approach:
We can solve this problem using Dynamic Programming (DP) with a 2D dp array to track maximum “pairs” achievable in subtrees. There are two conditions:
- Exclude current node: dp[0][u] stores the maximum pairs possible without including node u itself.
- Include current node: dp[1][u] stores the maximum pairs possible by including u in a matching with a child.
A Depth-First Search (DFS) calculates optimal values for dp at each node based on its children. Finally, the maximum number of pairs in a perfect matching is the maximum between dp[0][0] (excluding root) and dp[1][0] (including root).
Step by Step Algorithm:
- Initialization: For each node u, initialize dp[0][u] to 0 and dp[1][u] to negative infinity.
- DFS (Depth-First Search): Perform a DFS traversal on the tree.
- For each child v of node u:
- Recursively call DFS on child node v.
- Update dp[0][u]: Add the maximum of dp[1][v] (pairs including v) and dp[0][v] (pairs excluding v) to dp[0][u]. This represents the maximum pairs possible in the subtree rooted at u without including u.
- Update dp[1][u]: Calculate the difference between dp[0][v] and dp[1][v]. This represents the maximum number of pairs gained by including u in the matching with child v compared to the case where v is not included. Choose the maximum between the current dp[1][u] and this difference. This ensures we select the scenario that leads to the most pairs when including u.
- Final Update: After processing all children, update dp[1][u] by adding dp[0][u]. This incorporates the pairs possible without including u to the total pairs when u is included.
- Output: After the DFS traversal, the maximum number of pairs is the maximum value between dp[0][0] (excluding root) and dp[1][0] (including root).
Below is the implementation of the above algorithm:
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define ll long long
// Represents infinity
const ll INF = 10000000000000;
// Maximum number of nodes
const ll MX = 2e5 + 5;
// Adjacency list
vector<ll> Adj[MX];
// Dynamic programming array
ll dp[2][MX];
// Depth-first search to compute the maximum number of pairs
// u: current node
// p: parent node
void DFS(ll u, ll p)
{
// Initialize dp values
// Maximum number of pairs without including the current
// node
dp[0][u] = 0;
// Maximum number of pairs including the current node
dp[1][u] = -INF;
// Traverse through each adjacent node
for (ll v : Adj[u]) {
if (v == p)
// Skip if it's the parent node
continue;
// Recursively call DFS for child node
DFS(v, u);
// Update dp values
dp[0][u] += max(
dp[1][v],
// Add maximum pairs without including the child
dp[0][v]);
ll opt = min(dp[0][v] - dp[1][v],
// Difference between including and
// excluding the child
(long long)0);
// Update maximum pairs including the current node
dp[1][u] = max(dp[1][u], opt);
}
// Update dp[1] value
// Add pairs without the current node
dp[1][u] += dp[0][u];
// Add the current node to the matching
dp[1][u]++;
}
int main()
{
// Number of nodes
ll n = 10;
// Edges of the tree
ll edges[][2] = { { 5, 8 }, { 4, 6 }, { 9, 1 },
{ 10, 4 }, { 1, 3 }, { 2, 3 },
{ 7, 9 }, { 6, 2 }, { 5, 10 } };
// Build adjacency list
for (ll i = 0; i < n - 1; ++i) {
// Convert to 0-based indexing
ll a = edges[i][0] - 1;
// Convert to 0-based indexing
ll b = edges[i][1] - 1;
Adj[a].push_back(b);
// Undirected tree, add edge in both directions
Adj[b].push_back(a);
}
// Start DFS from root node (0)
DFS(0, -1);
// Output the maximum number of pairs
ll ans = max(dp[0][0], dp[1][0]);
cout << "Maximum number of edges in a matching: " << ans
<< endl;
return 0;
}
import java.util.ArrayList;
public class MaximumMatchingPairs {
// Represents infinity
static final long INF = 10000000000000L;
// Maximum number of nodes
static final int MX = 200005;
// Adjacency list
static ArrayList<Integer>[] Adj = new ArrayList[MX];
// Dynamic programming array
static long[][] dp = new long[2][MX];
// Depth-first search to compute the maximum number of
// pairs u: current node p: parent node
static void DFS(int u, int p)
{
// Initialize dp values
// Maximum number of pairs without including the
// current node
dp[0][u] = 0;
// Maximum number of pairs including the current
// node
dp[1][u] = -INF;
// Traverse through each adjacent node
for (int v : Adj[u]) {
if (v == p)
// Skip if it's the parent node
continue;
// Recursively call DFS for child node
DFS(v, u);
// Update dp values
dp[0][u] += Math.max(dp[1][v], dp[0][v]);
long opt = Math.min(dp[0][v] - dp[1][v], 0);
// Update maximum pairs including the current
// node
dp[1][u] = Math.max(dp[1][u], opt);
}
// Update dp[1] value
// Add pairs without the current node
dp[1][u] += dp[0][u];
// Add the current node to the matching
dp[1][u]++;
}
public static void main(String[] args)
{
// Number of nodes
int n = 10;
// Edges of the tree
int[][] edges = { { 5, 8 }, { 4, 6 }, { 9, 1 },
{ 10, 4 }, { 1, 3 }, { 2, 3 },
{ 7, 9 }, { 6, 2 }, { 5, 10 } };
for (int i = 0; i < MX; i++) {
Adj[i] = new ArrayList<>();
}
// Build adjacency list
for (int i = 0; i < n - 1; ++i) {
int a = edges[i][0] - 1;
int b = edges[i][1] - 1;
Adj[a].add(b);
Adj[b].add(a);
}
// Start DFS from root node (0)
DFS(0, -1);
// Output the maximum number of pairs
long ans = Math.max(dp[0][0], dp[1][0]);
System.out.println(
"Maximum number of edges in a matching: "
+ ans);
}
}
// This code is contributed by shivamgupta310570
# Represents infinity
INF = 10000000000000
# Maximum number of nodes
MX = 200005
# Adjacency list
Adj = [[] for _ in range(MX)]
# Dynamic programming array
dp = [[0] * MX for _ in range(2)]
# Depth-first search to compute the maximum number of pairs
# u: current node
# p: parent node
def DFS(u, p):
# Initialize dp values
# Maximum number of pairs without including the current node
dp[0][u] = 0
# Maximum number of pairs including the current node
dp[1][u] = -INF
# Traverse through each adjacent node
for v in Adj[u]:
if v == p:
# Skip if it's the parent node
continue
# Recursively call DFS for child node
DFS(v, u)
# Update dp values
dp[0][u] += max(dp[1][v], dp[0][v])
opt = min(dp[0][v] - dp[1][v], 0)
# Update maximum pairs including the current node
dp[1][u] = max(dp[1][u], opt)
# Update dp[1] value
# Add pairs without the current node
dp[1][u] += dp[0][u]
# Add the current node to the matching
dp[1][u] += 1
# Number of nodes
n = 10
# Edges of the tree
edges = [[5, 8], [4, 6], [9, 1], [10, 4], [
1, 3], [2, 3], [7, 9], [6, 2], [5, 10]]
# Build adjacency list
for edge in edges:
# Convert to 0-based indexing
a = edge[0] - 1
# Convert to 0-based indexing
b = edge[1] - 1
Adj[a].append(b)
# Undirected tree, add edge in both directions
Adj[b].append(a)
# Start DFS from root node (0)
DFS(0, -1)
# Output the maximum number of pairs
ans = max(dp[0][0], dp[1][0])
print("Maximum number of edges in a matching:", ans)
// Represents infinity
const INF = 10000000000000;
// Maximum number of nodes
const MX = 2e5 + 5;
// Adjacency list
let Adj = new Array(MX).fill().map(() => []);
// Dynamic programming array
let dp = new Array(2).fill().map(() => new Array(MX).fill(0));
// Depth-first search to compute the maximum number of pairs
// u: current node
// p: parent node
function DFS(u, p) {
// Initialize dp values
// Maximum number of pairs without including the current node
dp[0][u] = 0;
// Maximum number of pairs including the current node
dp[1][u] = -INF;
// Traverse through each adjacent node
for (let v of Adj[u]) {
if (v === p)
// Skip if it's the parent node
continue;
// Recursively call DFS for child node
DFS(v, u);
// Update dp values
dp[0][u] += Math.max(
dp[1][v],
// Add maximum pairs without including the child
dp[0][v]);
let opt = Math.min(dp[0][v] - dp[1][v], 0);
// Update maximum pairs including the current node
dp[1][u] = Math.max(dp[1][u], opt);
}
// Update dp[1] value
// Add pairs without the current node
dp[1][u] += dp[0][u];
// Add the current node to the matching
dp[1][u]++;
}
// Number of nodes
let n = 10;
// Edges of the tree
let edges = [ [ 5, 8 ], [ 4, 6 ], [ 9, 1 ],
[ 10, 4 ], [ 1, 3 ], [ 2, 3 ],
[ 7, 9 ], [ 6, 2 ], [ 5, 10 ] ];
// Build adjacency list
for (let i = 0; i < n - 1; ++i) {
// Convert to 0-based indexing
let a = edges[i][0] - 1;
// Convert to 0-based indexing
let b = edges[i][1] - 1;
Adj[a].push(b);
// Undirected tree, add edge in both directions
Adj[b].push(a);
}
// Start DFS from root node (0)
DFS(0, -1);
// Output the maximum number of pairs
let ans = Math.max(dp[0][0], dp[1][0]);
console.log("Maximum number of edges in a matching:", ans);
Output
Maximum number of edges in a matching: 5
Time Complexity : O(V)
Space Complexity : O(V)