567. Fewest Nodes to Guard Every Edge
Place guards on nodes of a tree. An edge is guarded when at least one of its two endpoints holds a guard. Print the smallest number of guards that guards EVERY edge.
4 nodes, edges 1-2 1-3 3-4 -> 2 guards on 1 and 3
5 nodes in a star -> 1 the centre guards all four edges
## The same shape as 566, inverted
In 566 the constraint was that no two CHOSEN nodes are adjacent. Here the constraint is that no two UNCHOSEN nodes are adjacent, because an edge with neither endpoint guarded is an unguarded edge.
So the two problems are complements of each other, and the recurrence has the same shape with the roles of the branches exchanged.
## Two numbers per node
take[u] = fewest guards in u's subtree, with a guard on u
skip[u] = fewest guards in u's subtree, with no guard on u
If u holds a guard, every edge down to a child is already guarded, so each child is free:
take[u] = 1 + sum over children c of min(take[c], skip[c])
If u holds no guard, every edge down to a child must be guarded by the child itself:
skip[u] = sum over children c of take[c]
The answer is min(take[root], skip[root]).
A leaf sets take = 1 and skip = 0, and the skip branch of its parent is what forces the
guard upwards when it is needed.
## Why the greedy on leaves is the same thing
There is a well known greedy here: repeatedly take a node that has a leaf child, guard it, and delete everything it covers. That greedy is correct, and it is exactly what this table discovers, one node at a time, from the bottom.
Writing the table is worth doing anyway, because the greedy stops working the moment the problem gains a weight or a second constraint, and the table does not.
## A check worth knowing
On any tree, the fewest guards here equals the largest set of edges no two of which share an endpoint. That is Koenig's theorem, and problem 578 in this topic computes the other side of it. Every tree in both test sets agrees, which is a genuinely independent check on both.
## Boundaries
A single node has no edges, so nothing needs guarding and the answer is 0. That is the case a solution that starts by placing a guard at the root gets wrong.
A single edge answers 1, either endpoint.
## 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 fewest guards needed so that every edge has a guarded endpoint.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.