[POI2009]救火站Gas

时间限制:10s      空间限制:162MB

题目描述

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


题目来源

没有写明来源

Menuappsclose