Graph Theory37 sections · 1633 units
Open in Course

Problem - Tree Matching

(CSES - Max matching)

Tree Diameter required thinking about paths. Now we move to a different type of problem: matching edges.

Given a tree, find the maximum matching: the largest set of edges where no two edges share a node. This is a classic subtree DP problem with states.

Think: What information do you need to track at each node? How does a node's decision affect its parent? You need 22 states per node: matched (this node is part of a selected edge) and unmatched (it is not).