tree-matching

Tree Matching

CSES medium

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?

Input:

First line: integer n — number of nodes (1..n).
Next n-1 lines: edges a b describing an undirected tree edge.

Output:

Print one integer: the maximum size of a matching.

Constraints:

1 ≤ n ≤ 2 · 10^5

Example:

Input:

Output:

Explanation: One possible matching is (1,2) and (3,4).

Solution

We want the largest set of edges such that no two chosen edges share an endpoint.

On a tree, we can solve this with DP after rooting the tree. The key local choice is whether a node is already “used” by matching it with its parent, because then it cannot match with any child.

DP idea

Root the tree at node 1. For each node v, compute:

dp0[v]: maximum matching size in the subtree of v when v is NOT matched with its parent (so v is free: it may match with at most one of its children, or none)
dp1[v]: maximum matching size in the subtree of v when v IS matched with its parent (so v is already used, cannot match with any child)

Answer will be dp0[root] because the root has no parent.

Recurrence

Let children(v) be neighbors except the parent.

1) If `v` is matched with its parent (`dp1[v]`)

Then v cannot match with children, so each child c must be in state “not matched with parent”:

[ dp1[v] = _{c children(v)} dp0[c] ]

2) If `v` is NOT matched with its parent (`dp0[v]`)

Two possibilities:

v matches with no child then all children are independent in state dp0:

[ base = _{c} dp0[c] ]

v matches with exactly one child u choosing edge (v,u) adds +1, and forces child u to be matched with its parent (dp1[u]). All other children remain dp0.

So if we match v with a specific child u, total is:

[ base - dp0[u] + dp1[u] + 1 ]

We choose the best u, or choose none:

[ dp0[v] = (base, _{u children(v)} (base - dp0[u] + dp1[u] + 1)) ]

SRTBOT proof

S — State

dp0[v] = best matching size inside subtree of v when v is free with respect to its parent. dp1[v] = best matching size inside subtree of v when v is already matched to its parent.

These states cover all possibilities because the only interaction between a subtree and the rest of the tree is through the edge to the parent.

R — Recurrence

If v is used by its parent (dp1[v]), it cannot be endpoint of any other matching edge → it cannot match with children → sum of dp0 over children.
If v is free (dp0[v]), it may match with at most one child. Either match none (base) or match one child u, converting only that child’s state to dp1[u] and adding 1 edge.

Thus the formulas above are necessary and sufficient.

T — Transition

Compute children first via DFS, then:

base = sum(dp0[child])
dp1[v] = base
dp0[v] = max(base, max(base - dp0[u] + dp1[u] + 1))

B — Base cases

For a leaf node v:

No children → sums are 0
dp1[v] = 0 (can’t match with children)
dp0[v] = 0 (no child to match with)

Correct.

O — Order of computation

Post-order DFS: compute DP for children before parent. Each node uses only children DP values, so dependencies are satisfied.

T — Time and space complexity

Each edge is processed a constant number of times.

Time: O(n)
Space: O(n) for adjacency + DP + recursion.

Final answer

Print dp0[1] after computing DP from root 1.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> g;
vector<long long> dp0, dp1;

void dfs(int v, int p) {
    long long base = 0;

    // First: solve children
    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v);
        base += dp0[to];
    }

    // If v is matched with parent -> cannot match any child
    dp1[v] = base;

    // If v is not matched with parent -> either match with no child, or with exactly one child
    dp0[v] = base;

    for (int u : g[v]) {
        if (u == p) continue;
        long long candidate = base - dp0[u] + dp1[u] + 1; // match (v,u)
        dp0[v] = max(dp0[v], candidate);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    g.assign(n + 1, {});
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dp0.assign(n + 1, 0);
    dp1.assign(n + 1, 0);

    int root = 1;
    dfs(root, -1);

    cout << dp0[root] << "\n";
    return 0;
}