H. [USACO08JAN] Cell Phone Network G

Type: RemoteJudge

1000ms

125MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Farmer John 想让他的所有牛用上手机以便相互交流。他需要建立几座信号塔在 $N$ 块草地中。已知与信号塔相邻的草地和信号塔所在的草地均能收到信号。给你 $N-1$ 个草地 $(A,B)$ 的相邻关系，问：最少需要建多少个信号塔能实现所有草地都有信号。

第 $1$ 行：一个整数 $N$ 。

第 $2$ 行到第 $N$ 行：每一行两个整数，用空格分隔，给出一对相邻的草地 $A$ 和 $B$ 。

一个整数，表示要安装的最少信号塔数。

对于所有的数据， $1 \leq N \leq 10^4$ ， $1 \leq A,B \leq N$ ， $A \neq B$ 。