No submission language available for this problem.

题目描述

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