信号塔覆盖(Cell Phone Network G)

题目描述

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

输入格式

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

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

输出格式

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

样例输入 #1

5
1 3
5 2
4 3
3 5

样例输出 #1

2

数据范围

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

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1500。

测试点分布

出处：原题链接