P2899 [USACO08JAN] Cell Phone Network G

Farmer John wants all his cows to use cell phones so that they can communicate. He needs to build several cell towers among $N$ pastures. A tower provides coverage to the pasture it is placed on and to any pasture adjacent to it. You are given $N-1$ adjacency pairs $(A, B)$ between pastures. What is the minimum number of towers required so that every pasture has coverage?

Line 1: an integer $N$. Lines 2 through $N$: each line contains two integers separated by a space, giving one adjacent pair of pastures $A$ and $B$.

A single integer, the minimum number of towers to install.

For all testdata, $1 \leq N \leq 10^4$, $1 \leq A, B \leq N$, $A \neq B$. Translated by ChatGPT 5