Cell Phone Network

Interview

Time limit1sMemory limit128 MB

Summary

Given a tree of N pastures, choose the fewest vertices so that every vertex is chosen or adjacent to a chosen one.

Level: Medium6 of 10
Topics: Tree, Dynamic programming, Greedy, DFS
Solved: No attempts yet

Problem

Farmer John has decided to give each of his cows a cell phone to encourage their social interaction. To let the cows communicate, he must install cell phone towers on his $N$ pastures (conveniently numbered $1$ through $N$ ).

Exactly $N-1$ pairs of pastures are adjacent, and for any two pastures $A$ and $B$ there is a sequence of adjacent pastures leading from $A$ to $B$ . In other words, the pastures form a tree.

Towers can only be placed on pastures. A tower placed on a pasture provides service to that pasture and to every pasture adjacent to it.

Determine the minimum number of towers Farmer John must install so that every pasture receives cell phone service.

Constraint: $1 \le N \le 10000$ .

Input

Line 1: a single integer $N$ ( $1 \le N \le 10000$ ).
Lines 2 to $N$ : each line contains two space-separated integers $A$ and $B$ describing a pair of adjacent pastures ( $1 \le A, B \le N$ , $A \ne B$ ).

Output

A single integer: the minimum number of towers needed so that every pasture receives service.

Hint

The picture below shows one example with $5$ pastures whose adjacencies form a tree.

   4  2
   |  |
1--3--5

A tower on pasture $3$ serves pastures $1, 3, 4$ , and $5$ ; adding one more tower on pasture $2$ (or $5$ ) covers the rest. Since each tower serves itself and its neighbors, the goal is to place towers so that their combined coverage reaches every pasture.

Examples3

Example 1
Input
```
5
1 3
5 2
4 3
3 5
```
Expected output
```
2
```
Example 2
Input
```
2
1 2
```
Expected output
```
1
```
Example 3
Input
```
3
1 2
2 3
```
Expected output
```
1
```