#1117. [POI2009]救火站Gas

题目描述

给你一棵树，现在要建立一些消防站，有以下要求: 1. 消防站要建立在节点上，每个节点可能建立不只一个消防站。 2. 每个节点应该被一个消防站管理，这个消防站不一定建立在该节点上。 3. 每个消防站可以管理至多s个节点。 4. 消防站只能管理距离（两点间最短路径的边数）不超过k的结点。请问至少要设立多少个消防站。

输入格式

第一行n,s,k。接下来n-1行每行xi,yi描述一条边连接xi与yi。 1<=n<=100000 1<=s<=n 1<=k<=20 1<=xi

输出格式

一个数，最少的消防站个数。

样例

样例输入

12 3 1  

1 12  

3 8  

7 8  

8 9  

2 12  

10 12  

9 12  

4 8  

5 8  

8 11  

6 8  

样例输出

4  

![image](./118/file/1117.jpg)

数据范围与提示

感谢MT大牛贡献译文.