The Most Edges With No Shared Endpoint
Choose a set of edges of a tree so that no two chosen edges share an endpoint. Print the largest number of edges such a set can have.
4 nodes, edges 1-2 1-3 3-4 -> 2 the edges 1-2 and 3-4
5 nodes in a star -> 1 every edge touches the centre
## Decide at the parent
Edges are awkward objects to run a table over, so rewrite the choice in terms of NODES.
Rooted at node 1, every edge is "some node and its parent", so the question at each node u is
whether the edge from u up to its parent is chosen.
That single bit is what the parent needs, so the state is:
free[u] = best in u's subtree, with u NOT matched to any of its children
used[u] = best in u's subtree, with u matched to one of its children
Only free[u] is usable by the parent, since a node cannot be in two chosen edges.
## The recurrence
Let base = sum over children c of max(free[c], used[c]), which is the best if u matches
nothing below it:
free[u] = base
used[u] = max over children c of base - max(free[c], used[c]) + free[c] + 1
Reading that second line: pick one child c to match u with, refund whatever c was
contributing, charge free[c] instead because c must now be unmatched below, and add 1 for
the edge just taken.
The answer is max(free[root], used[root]).
## Why the refund form
Written naively this is a nested loop: for each child, re-add the contributions of all the
others. That is quadratic in the degree, and a star of 100000 leaves makes it 10^10 steps.
Computing base once and adjusting one term is the standard fix, and it appears whenever a
node must single out one child.
## The check from 567
On any tree this answer equals the fewest guards in problem 567. That is Koenig's theorem, and every test in both problems agrees, which is a real check rather than a restatement: the two tables are different and are computed from different recurrences.
## Boundaries
A single node has no edges, so the answer is 0.
A star answers 1 however many leaves it has, since every edge meets the centre.
## Cost
Time O(n). Space O(n).