SP15568 STC01 - Fire Extinguishers

Byteasar 刚建了一座新的宫殿，这个宫殿由 $N$ 个房间和 $N-1$ 条走廊连接而成。每条走廊连接着两个房间。房间编号从 $1$ 到 $N$。宫殿只有一个入口，通向房间 $1$。对于每个房间，从入口只存在一条惟一的无回头路径到达它。换句话说，这些房间和走廊构成了一棵树——一个连通而没有环的图。 消防监管人员要求在房间内放置灭火器，具体要求如下： - 灭火器可以放置在某些房间，一个房间可以存放多个灭火器。 - 每个房间都需要有一个灭火器保护，但这个灭火器可以放在另一个房间中。 - 每个灭火器最多可以保护 $S$ 个房间。 - 对于每个房间，其保护的灭火器必须在 $K$ 条走廊之内的距离范围内。 由于 Byteasar 喜欢奢华的宫殿，因此他在刚刚完成另一个宏伟的宫殿建造后资金短缺。所以他希望知道要满足消防要求，最少需要多少个灭火器。

第一行由三个整数 $N$、$S$ 和 $K$ 组成，空格分隔，表示房间数量、每个灭火器的最大保护房间数和灭火器的最大有效距离，满足 $1 \le N \le 100000$，$1 \le S \le N$，$1 \le K \le 20$。接下来的 $N-1$ 行中，每行包含两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 条走廊连接房间 $X_i$ 和 $Y_i$。

输出一个整数，表示需要安装的最小灭火器数量。 ## 示例 **输入:** ``` 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 ``` **本翻译由 AI 自动生成**