#1117. [POI2009]救火站Gas

内存限制:162 MiB 时间限制:10 Sec

题目描述

给你一棵树,现在要建立一些消防站,有以下要求: 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

数据范围与提示

感谢MT大牛贡献译文.