P83347

信号站

难度 初三 动态规划 树形dp
讨论 统计 1通过 1提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

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

输入

第1行:单个整数N(1 ≤ N ≤ 10,000)。
第2..N行:每行用两个空格分隔的整数指定一对相邻的牧场:A和B。

输出

1行:单个整数,表示要安装的塔的最小数量。

样例

样例 1
输入
5
1 3
5 2
4 3
3 5
输出
2
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交