All submissions for this problem are available.
Farmer John has decided to give each of his cows a cell phone in
hopes to encourage their social interaction. This, however, requires
him to set up cell phone towers on his N (1 <= N <= 10,000) pastures
(conveniently numbered 1..N) so they can all communicate.
Exactly N-1 pairs of pastures are adjacent, and for any two pastures
A and B (1 <= A <= N; 1 <= B <= N; A != B) there is a sequence of
adjacent pastures such that A is the first pasture in the sequence
and B is the last. Farmer John can only place cell phone towers in
the pastures, and each tower has enough range to provide service
to the pasture it is on and all pastures adjacent to the pasture
with the cell tower.
Help him determine the minimum number of towers he must install to
provide cell phone service to each pasture.
INPUT FORMAT:* Line 1: A single integer: N * Lines 2 to N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B
SAMPLE INPUT:5 1 3 5 2 4 3 3 5
INPUT DETAILS: Farmer John has 5 pastures: pastures 1 and 3 are adjacent, as are pastures 5 and 2, pastures 4 and 3, and pastures 3 and 5. Geometrically, the farm looks like this (or some similar configuration) 4 2 | | 1--3--5
OUTPUT FORMAT:* Line 1: A single integer indicating the minimum number of towers to install
SAMPLE OUTPUT:2 OUTPUT DETAILS: The towers can be placed at pastures 2 and 3 or pastures 3 and 5.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.