⚙️AlgorithmIntermediate

Tree DP - Matching and Covering

Key Points

  • •
    Tree DP solves matching, vertex cover, and independent set on trees in linear time using small state transitions per node.
  • •
    Maximum matching on a tree uses two states per node to decide whether the node is matched to one of its children or not.
  • •
    Minimum vertex cover on a tree also uses two states: include the node or exclude it, with forced choices on children when excluded.
  • •
    The size of a maximum independent set equals n minus the size of a minimum vertex cover; on trees this is easy to compute by DP.
  • •
    Trees are bipartite, so by Kőnig’s theorem the size of a maximum matching equals the size of a minimum vertex cover.
  • •
    Weighted versions of vertex cover (and independent set) are handled by the same DP with weights added when a node is included.
  • •
    All these DPs run in O(n) time and O(n) space because a tree has n-1 edges and each edge is processed a constant number of times.
  • •
    You can also reconstruct the actual matching/cover/independent set with a second DFS that follows the DP choices.

Prerequisites

  • →Trees and rooting — You must understand how to root a tree and iterate over children (skipping the parent) to structure DP.
  • →Depth-first search (DFS) and postorder — Tree DP relies on processing children before parents; DFS provides a natural postorder traversal.
  • →Dynamic programming basics — You need to be comfortable defining states and transitions and combining subproblem results.
  • →Graph representations (adjacency lists) — Efficient O(n) traversal requires adjacency lists rather than dense matrices.
  • →Big-O notation — To analyze time and space complexity such as O(n) for tree algorithms.
  • →Bipartite graphs — Trees are bipartite; this underlies Kőnig’s theorem and useful cross-checks between matching and cover.
  • →Integer overflow awareness — Weighted DPs may require 64-bit integers to safely store sums.

Detailed Explanation

Tap terms for definitions

01Overview

Imagine a company hierarchy (a tree). You want to pair some employees for mentoring so that no employee is in two pairs (this is a matching), or you want to select a minimal set of supervisors so that every reporting line touches at least one selected supervisor (this is a vertex cover). Alternatively, you might want to pick as many employees as possible such that no two are directly connected in the hierarchy (an independent set). On general graphs these are hard problems, but on trees they become beautifully simple with dynamic programming (DP). The core idea of Tree DP is to root the tree and define a small, precise meaning for each DP state at a node: for example, whether the node is included in a set (cover/independent set) or matched to a child (matching). Then, process nodes bottom-up and combine children’s results with simple formulas that reflect the constraints of the problem. Example: for minimum vertex cover, if a node is excluded, all its children must be included to cover the parent-child edges; if it’s included, each child can be chosen or not, whichever is cheaper. This leads to linear-time recurrences. Similar two-state ideas solve maximum matching and maximum independent set. Weighted versions follow the exact same pattern—with weights added when you include a node.

02Intuition & Analogies

Think of edges as communication lines that need supervision (vertex cover). If you don’t place a supervisor at a manager, then every direct report must be a supervisor to cover the lines to that manager. But if you do place a supervisor at the manager, you give the children freedom: each child can be a supervisor or not, whichever is cheaper. That is exactly the DP transition. For matching, think of forming pairs along the hierarchy. A person can be paired with at most one neighbor. If a node is not paired with any child, all children solve their own pairing problems independently. If it pairs with one chosen child, you gain one matched edge, and all other children continue independently. This creates a simple “best gain” choice over which child to pair with. For independent set, imagine placing flags on employees so that no adjacent employees both get flags. If you flag a node, you must not flag its children; if you don’t flag it, each child may choose to be flagged or not, whichever yields more flags. This is the mirror image of vertex cover. In fact, the complement of any vertex cover is an independent set—so minimizing one maximizes the other. The tree’s lack of cycles means local choices don’t unexpectedly interact through loops. So we can compute answers bottom-up in one pass, and each parent only needs its children’s already-solved answers.

03Formal Definition

Let T = (V, E) be a rooted tree with root r. - Maximum matching: A matching M E such that no two edges in M share a common endpoint, maximizing . Define DP states for each node v: [v] is the maximum matching size in the subtree of v when v is not matched to its parent; [v] is when v is matched to its parent. Transitions combine children’s states and possibly match v with exactly one child. - Minimum vertex cover: A vertex set C V that covers every edge (each edge has at least one endpoint in C), minimizing . States: [v] is the minimum cover size in v’s subtree when v is excluded; [v] is when v is included. If v is excluded, all children must be included; if v is included, each child chooses min of included/excluded. - Maximum independent set: A set I V with no edge inside I, maximizing . States: [v] is the maximum independent set size in v’s subtree when v is excluded; [v] is when v is included. If v is included, exclude all children; otherwise, take max per child. For any graph, + = , so on trees MIS size can also be obtained from the vertex cover. Weighted versions (e.g., weighted vertex cover) replace counts with weight sums and add node weight when a node is included.

04When to Use

  • Your graph is guaranteed to be a tree (or a forest). Many contest problems state “n nodes, n-1 edges, connected,” which means a tree; or multiple components mean a forest you can handle component-wise.
  • You need maximum matching, minimum vertex cover, or maximum independent set—unweighted or weighted. On general graphs these can be NP-hard or require heavy machinery, but on trees, a simple DP suffices.
  • You must reconstruct the actual set/edges, not just compute sizes. Tree DP can return choices by running a second DFS that follows the DP’s argmin/argmax decisions.
  • Constraints are large (n up to 2e5). Since a tree has exactly n-1 edges, and our transitions scan each edge a constant number of times, linear-time solutions are ideal for tight time limits.
  • The problem involves “include/exclude” or “paired/not paired” logic across parent-child relations. This structure strongly hints at 2-state per node DP that mirrors the local constraint.
  • You want to leverage relationships like Kőnig’s theorem (trees are bipartite) to cross-check: maximum matching size equals minimum vertex cover size, and MIS size equals n minus MVC size.

⚠️Common Mistakes

  • Confusing DP states: For matching, dp_{1}[v] should mean “v is matched to its parent,” not “v is matched to a child.” Mixing these meanings breaks transitions. Define states precisely and stick to them.
  • Double counting children or allowing a node to be matched to more than one child. The matching transition must select at most one child to pair with v, typically via a single best gain over children.
  • Forgetting to root the tree and to skip the parent during child iteration. Always pass the parent or precompute a parent array to avoid back-edges.
  • Stack overflows with deep recursion on large trees. Use an explicit stack for iterative DFS or increase recursion limits if the environment allows.
  • Wrong base cases on leaves. Ensure formulas work on degree-1 nodes: sums over empty sets should be zero, and max with zero should be handled explicitly.
  • Reconstructing solutions without mirroring DP choices. During reconstruction, enforce the same constraints: if a vertex is excluded in a vertex cover, all children must be included; if included, pick the child’s better state. For matching, ensure you only select the unique child that gave the best gain (if any).
  • Using 32-bit ints for weighted sums that can overflow. Use 64-bit (long long) for weights and DP values when weights are large.

Key Formulas

Tree Matching DP

Explanation: dp1[v] is the best when v is matched to its parent, so v cannot match any child; each child u behaves as not matched to parent (dp0[u]). dp0[v] optionally matches v with exactly one child u, gaining 1 plus dp1[u], with all other children contributing dp0.

Tree Vertex Cover DP

Explanation: If v is excluded (state 0), all children must be included (state 1) to cover edges (v,u). If v is included (state 1), each child independently chooses the cheaper of included or excluded, and we add 1 for choosing v.

Weighted VC DP

Explanation: Same structure as unweighted, but when including v we add its weight instead of 1. Values are total weights rather than counts.

Tree MIS DP

Explanation: If v is included (state 1), none of its children can be included, so we take is0 for each child. If v is excluded (state 0), each child picks its better state.

Independent Set vs. Vertex Cover

Explanation: For any graph G, the size of a maximum independent set (alpha) plus the size of a minimum vertex cover (tau) equals the number of vertices. The complement of a vertex cover is an independent set and vice versa.

Kőnig’s Theorem

Explanation: In bipartite graphs, the maximum matching size (nu) equals the minimum vertex cover size (tau). Trees are bipartite, so this holds for all trees.

Tree Edge Count

Explanation: A connected acyclic graph with n vertices has exactly n-1 edges. This underpins linear-time DP because we process each edge a constant number of times.

Linear Complexity on Trees

Explanation: On trees, algorithms that visit each vertex and edge once run in linear time, simplifying complexity bounds for Tree DP.

Complexity Analysis

All presented Tree DP algorithms run in linear time and space. A tree with n nodes has exactly n−1 edges, so a single DFS or postorder traversal that touches each edge a constant number of times leads to O(n) time. Specifically, every DP transition iterates over a node’s children once, and the total sum of children over all nodes equals n−1. Optional reconstruction also processes each edge and node once, preserving O(n) time. Space-wise, we store adjacency lists of total size O(n), a parent array and an order or recursion stack O(n), and a constant number of DP arrays such as dp0, dp1, or is0, is1—each O(n). Therefore, total auxiliary memory is O(n). When using recursion, the call stack can grow to O(n) in the worst case (e.g., a path), which may risk stack overflow in some environments. An iterative DFS with an explicit stack avoids this and still runs in O(n) space. For weighted versions, data types should be 64-bit integers if weights are large to avoid overflow; this does not affect asymptotic complexity. For forests (multiple components), we run the DP on each root and sum or combine results; the complexity remains O(n) because total nodes and edges over all components still sum to O(n). Thus, both unweighted and weighted maximum matching, minimum vertex cover, and maximum independent set on trees are solvable in linear time and space, making them ideal for large constraints typical of competitive programming.

Code Examples

Maximum Matching Size on a Tree (Iterative Postorder DP)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Compute maximum matching size on a tree using two-state DP per node.
5// State meaning:
6//   dp0[v]: best matching size in the subtree of v when the edge (parent,v) is NOT used
7//   dp1[v]: best matching size in the subtree of v when the edge (parent,v) IS used (v matched to parent)
8// Transitions:
9//   dp1[v] = sum over children u of dp0[u]
10//   dp0[v] = sum dp0[u] + max(0, max over children u of (1 + dp1[u] - dp0[u]))
11// Answer: dp0[root]
12
13int main() {
14    ios::sync_with_stdio(false);
15    cin.tie(nullptr);
16
17    int n; 
18    if (!(cin >> n)) return 0;
19    vector<vector<int>> g(n+1);
20    for (int i = 0; i < n-1; ++i) {
21        int u, v; cin >> u >> v;
22        g[u].push_back(v);
23        g[v].push_back(u);
24    }
25
26    // Root the tree at 1 (arbitrary). Build parent and postorder iteratively.
27    vector<int> parent(n+1, -1), order; order.reserve(n);
28    order.push_back(1);
29    parent[1] = 0;
30    for (size_t i = 0; i < order.size(); ++i) {
31        int v = order[i];
32        for (int u : g[v]) if (u != parent[v]) {
33            parent[u] = v;
34            order.push_back(u);
35        }
36    }
37    // Process in reverse order = postorder (children before parent)
38    vector<int> dp0(n+1, 0), dp1(n+1, 0);
39    for (int i = n-1; i >= 0; --i) {
40        int v = order[i];
41        long long sum0 = 0; // sum of dp0[child]
42        long long bestGain = 0; // best gain from matching v with exactly one child
43        for (int u : g[v]) if (u != parent[v]) {
44            sum0 += dp0[u];
45            long long gain = 1LL + dp1[u] - dp0[u];
46            if (gain > bestGain) bestGain = gain;
47        }
48        dp1[v] = (int)sum0;
49        dp0[v] = (int)(sum0 + max(0LL, bestGain));
50    }
51
52    cout << dp0[1] << "\n";
53    return 0;
54}
55

We root the tree at 1 and compute a postorder without recursion. For each node v, dp1[v] assumes v is matched to its parent, so v cannot match any child; all children contribute dp0. For dp0[v], we either do not match v with any child (sum of dp0 over children) or choose exactly one child u to match with, which adds a gain of 1 + dp1[u] − dp0[u]. We pick the best gain if positive. The result at the root (not matched to a parent) is dp0[1].

Time: O(n)Space: O(n)
Minimum Vertex Cover on a Tree with Reconstruction
1#include <bits/stdc++.h>
2using namespace std;
3
4// Minimum Vertex Cover on a tree with reconstruction of chosen nodes.
5// States:
6//   dp0[v]: min cover size in subtree when v is EXCLUDED
7//   dp1[v]: min cover size in subtree when v is INCLUDED
8// Transitions:
9//   dp0[v] = sum over children u of dp1[u]
10//   dp1[v] = 1 + sum over children u of min(dp0[u], dp1[u])
11// Answer: min(dp0[root], dp1[root])
12
13int main() {
14    ios::sync_with_stdio(false);
15    cin.tie(nullptr);
16
17    int n; 
18    if (!(cin >> n)) return 0;
19    vector<vector<int>> g(n+1);
20    for (int i = 0; i < n-1; ++i) {
21        int u, v; cin >> u >> v;
22        g[u].push_back(v);
23        g[v].push_back(u);
24    }
25
26    int root = 1;
27    vector<int> parent(n+1, -1), order; order.reserve(n);
28    parent[root] = 0; order.push_back(root);
29    for (size_t i = 0; i < order.size(); ++i) {
30        int v = order[i];
31        for (int u : g[v]) if (u != parent[v]) {
32            parent[u] = v;
33            order.push_back(u);
34        }
35    }
36
37    vector<int> dp0(n+1, 0), dp1(n+1, 0);
38    for (int i = n-1; i >= 0; --i) {
39        int v = order[i];
40        long long sum0 = 0, sum1 = 1; // sum0 builds dp0[v], sum1 builds dp1[v]
41        for (int u : g[v]) if (u != parent[v]) {
42            sum0 += dp1[u];
43            sum1 += min(dp0[u], dp1[u]);
44        }
45        dp0[v] = (int)sum0;
46        dp1[v] = (int)sum1;
47    }
48
49    // Reconstruction: collect the chosen nodes in one optimal cover
50    vector<int> cover;
51    cover.reserve(n);
52    vector<char> seen(n+1, 0);
53    // Stack: (v, take) where take=0 means v excluded; 1 means included
54    vector<pair<int,int>> st;
55    int startTake = (dp0[root] <= dp1[root]) ? 0 : 1;
56    st.push_back({root, startTake});
57    while (!st.empty()) {
58        auto [v, take] = st.back(); st.pop_back();
59        if (seen[v]) continue; seen[v] = 1;
60        if (take == 1) cover.push_back(v);
61        for (int u : g[v]) if (u != parent[v]) {
62            if (take == 0) {
63                // If v is excluded, child must be included
64                st.push_back({u, 1});
65            } else {
66                // If v is included, child picks cheaper state
67                int childTake = (dp0[u] <= dp1[u]) ? 0 : 1;
68                st.push_back({u, childTake});
69            }
70        }
71    }
72
73    cout << min(dp0[root], dp1[root]) << "\n";
74    // Optional: print the set (size and nodes)
75    // cout << cover.size() << "\n";
76    // for (int v : cover) cout << v << ' ';
77    // cout << "\n";
78
79    return 0;
80}
81

We compute dp0 and dp1 in postorder. Then we reconstruct one optimal vertex cover by a second pass: if the parent is excluded, the child must be included; if the parent is included, the child chooses whichever state yields a smaller DP value. The program prints the minimum cover size; code to print the chosen vertices is included but commented for flexibility.

Time: O(n)Space: O(n)
Weighted Minimum Vertex Cover on a Tree
1#include <bits/stdc++.h>
2using namespace std;
3
4// Weighted Minimum Vertex Cover on a tree.
5// Each node v has weight w[v]. We minimize the sum of chosen weights.
6// States:
7//   dp0[v]: min total weight in subtree when v is EXCLUDED
8//   dp1[v]: min total weight in subtree when v is INCLUDED
9// Transitions:
10//   dp0[v] = sum over children u of dp1[u]
11//   dp1[v] = w[v] + sum over children u of min(dp0[u], dp1[u])
12
13int main() {
14    ios::sync_with_stdio(false);
15    cin.tie(nullptr);
16
17    int n; 
18    if (!(cin >> n)) return 0;
19    vector<long long> w(n+1);
20    for (int i = 1; i <= n; ++i) cin >> w[i];
21
22    vector<vector<int>> g(n+1);
23    for (int i = 0; i < n-1; ++i) {
24        int u, v; cin >> u >> v;
25        g[u].push_back(v);
26        g[v].push_back(u);
27    }
28
29    int root = 1;
30    vector<int> parent(n+1, -1), order; order.reserve(n);
31    parent[root] = 0; order.push_back(root);
32    for (size_t i = 0; i < order.size(); ++i) {
33        int v = order[i];
34        for (int u : g[v]) if (u != parent[v]) {
35            parent[u] = v;
36            order.push_back(u);
37        }
38    }
39
40    const long long INF = (1LL<<62);
41    vector<long long> dp0(n+1, 0), dp1(n+1, 0);
42    for (int i = n-1; i >= 0; --i) {
43        int v = order[i];
44        long long a = 0;           // builds dp0[v]
45        long long b = w[v];        // builds dp1[v]
46        for (int u : g[v]) if (u != parent[v]) {
47            a += dp1[u];
48            b += min(dp0[u], dp1[u]);
49        }
50        dp0[v] = a;
51        dp1[v] = b;
52    }
53
54    cout << min(dp0[root], dp1[root]) << "\n";
55    return 0;
56}
57

This is the weighted analogue of the vertex cover DP. When including a node v, we add its weight w[v]; when excluding, we force all children into the included state. The program outputs the minimal total weight of a vertex cover.

Time: O(n)Space: O(n)
Maximum Independent Set on a Tree with Reconstruction
1#include <bits/stdc++.h>
2using namespace std;
3
4// Maximum Independent Set (MIS) on a tree with reconstruction.
5// States:
6//   is0[v]: maximum size in subtree when v is EXCLUDED from the set
7//   is1[v]: maximum size in subtree when v is INCLUDED in the set
8// Transitions:
9//   is1[v] = 1 + sum over children u of is0[u]
10//   is0[v] = sum over children u of max(is0[u], is1[u])
11
12int main() {
13    ios::sync_with_stdio(false);
14    cin.tie(nullptr);
15
16    int n; 
17    if (!(cin >> n)) return 0;
18    vector<vector<int>> g(n+1);
19    for (int i = 0; i < n-1; ++i) {
20        int u, v; cin >> u >> v;
21        g[u].push_back(v);
22        g[v].push_back(u);
23    }
24
25    int root = 1;
26    vector<int> parent(n+1, -1), order; order.reserve(n);
27    parent[root] = 0; order.push_back(root);
28    for (size_t i = 0; i < order.size(); ++i) {
29        int v = order[i];
30        for (int u : g[v]) if (u != parent[v]) {
31            parent[u] = v;
32            order.push_back(u);
33        }
34    }
35
36    vector<int> is0(n+1, 0), is1(n+1, 0);
37    for (int i = n-1; i >= 0; --i) {
38        int v = order[i];
39        long long a = 0; // is0[v]
40        long long b = 1; // is1[v]
41        for (int u : g[v]) if (u != parent[v]) {
42            a += max(is0[u], is1[u]);
43            b += is0[u];
44        }
45        is0[v] = (int)a;
46        is1[v] = (int)b;
47    }
48
49    // Reconstruction
50    vector<int> indep;
51    vector<pair<int,int>> st; // (v, take) where take=0 exclude, 1 include
52    int startTake = (is0[root] >= is1[root]) ? 0 : 1;
53    st.push_back({root, startTake});
54    vector<char> seen(n+1, 0);
55    while (!st.empty()) {
56        auto [v, take] = st.back(); st.pop_back();
57        if (seen[v]) continue; seen[v] = 1;
58        if (take == 1) indep.push_back(v);
59        for (int u : g[v]) if (u != parent[v]) {
60            if (take == 1) {
61                // If v included, child must be excluded
62                st.push_back({u, 0});
63            } else {
64                // If v excluded, child picks better of include/exclude
65                int childTake = (is0[u] >= is1[u]) ? 0 : 1;
66                st.push_back({u, childTake});
67            }
68        }
69    }
70
71    cout << max(is0[root], is1[root]) << "\n";
72    // Optional: print the independent set
73    // cout << indep.size() << "\n";
74    // for (int v : indep) cout << v << ' ';
75    // cout << "\n";
76
77    return 0;
78}
79

We compute MIS with two states per node. If we include a node, we must exclude all its children; if we exclude it, each child picks its better option. A second pass reconstructs one maximum independent set by mirroring these choices.

Time: O(n)Space: O(n)