578. 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).
Constraints - `1 ≤ n ≤ 100000` - the input is always a tree
Input
The first line contains an integer n, the number of nodes.
Each of the next n - 1 lines contains two integers u and v, an edge of
the tree. Nodes are numbered 1 to n and the tree is rooted at node 1.
Output
Print one integer, the largest number of edges no two of which share an endpoint.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.