568. Fewest Cameras to Watch Everything

A camera placed on a node watches that node and every node one edge away from it. Print the fewest cameras that leave NO node unwatched.

4 nodes, edges 1-2 1-3 3-4 -> 2 5 nodes in a star -> 1 a camera at the centre sees everything

## Not the same as 567

Problem 567 guarded every EDGE; this guards every NODE. The difference matters, and the answers really do differ: on the path of eight nodes, 567 answers 4 and this answers 3.

That is worth checking before writing any code, because the two problems look alike enough that the 567 recurrence is a tempting thing to reuse.

## Two numbers are not enough

The natural attempt keeps take and skip as before. It fails, because "no camera on u" is not one situation but two:

· u has no camera, but a child does, so u is already watched · u has no camera and no child has one, so u still needs its PARENT to hold one

The parent must distinguish those, because the second one obliges it. Two numbers cannot carry that, so the state has three values:

has[u] = fewest cameras in u's subtree, with a camera on u cov[u] = fewest, no camera on u, but u is watched by a child unc[u] = fewest, no camera on u, and u is not watched at all

## The recurrence

With a camera on u, every child is watched by u itself, so a child may be in any state:

has[u] = 1 + sum over children c of min(has[c], cov[c], unc[c])

For unc[u], no child may hold a camera, and every child must already be watched from below:

unc[u] = sum over children c of cov[c]

cov[u] is the interesting one. Each child contributes min(has[c], cov[c]), but at least ONE child must actually be in has. Take the plain minimum first, and if no child happened to choose has, pay the cheapest upgrade:

cov[u] = sum of min(has[c], cov[c]) + (0 if some child already chose has, else min over children of has[c] - cov[c])

The answer is min(has[root], cov[root]), because the root has no parent and so may not be left uncovered.

## The base case

A leaf has no children. It can hold a camera, for a cost of 1, or hold none and be uncovered, for 0. It cannot be covered from below, so cov at a leaf is IMPOSSIBLE, not zero.

Setting it to zero is the single most common bug here, and it produces answers that are too small. Use a large sentinel and make sure adding to it does not overflow.

## Boundaries

A single node needs one camera, since there is no parent to cover it. That is the case where cov[root] is impossible and has[root] is the only choice.

## Cost

Time O(n). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - the input is always a tree