#6321. 「雅礼国庆 2017 Day5」Repulsed

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

w 心里的火焰就要被熄灭了。
简便起见,假设小 w 的内心是一棵 n − 1 条边, n 个节点的树。
现在你要在每个节点里放一些灭火器,每个节点可以放任意多个。
接下来每个节点都要被分配给一个至多 k 条边远的灭火器,每个灭火器最多能分配给 s 个节点。
至少要多少个灭火器才能让小 w 彻底死心呢?

输入格式

第一行三个整数 n, s, k
接下来 n − 1 行每行两个整数表示一条边。

输出格式

一行一个整数表示答案。

样例

样例输入

10 10 3
1 8
2 3
1 5
2 4
1 2
8 9
8 10
5 6
5 7

样例输出

1

数据范围与提示

对于 20% 的数据满足 n \le 100,k \le 2
对于另外 20% 的数据满足 k = 1
对于另外 20% 的数据满足 s = 1
对于 100% 的数据满足 n \le 10^5, k \le 20, s \le 10^9