UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4346. [POI2016]Nadajniki

统计 下载数据

Description

比特镇一共有n个房子,编号依次为1到n,这些房子通过n-1条无向道路连通在一起,形成了一棵树的结构。
Bytesear要在比特镇实施Wifi搭建计划,他要让Wifi覆盖到比特镇的每一条道路。
Bytesear可以安置无限多个Wifi发射器,但是只能安置在树上的节点上,一个房子可以安置多个Wifi发射器。
对于一条道路(a,b),如果它满足以下两个条件之中的至少一个,那么这条边将被Wifi覆盖:
1.a点放置了Wifi发射器或者和b点放置了Wifi发射器。
2.与a点或b点直接相邻的点中,至少放置了两个Wifi发射器。
请帮助Bytesear规划一个最优的放置方案,使得Wifi覆盖到比特镇的每一条道路,且放置的Wifi发射器总数尽可能少。

Input

第一行包含一个正整数n(2<=n<=200000),表示房子的总数。
接下来n-1行,每行两个正整数a,b(1<=a,b<=n),表示a点和b点之间有一条边。

Output

输出一行一个整数,即最少的Wifi发射器总数。

Sample Input

7
1 2
2 3
4 3
5 4
6 3
7 6

Sample Output

2

Hint

在3号点放置两个Wifi发射器。


Source

鸣谢Claris