P3479 [POI 2009] GAS-Fire Extinguishers

Byteasar 新建了一座宫殿。它由 $n$ 个房间和 $n-1$ 条走廊连接而成。每条走廊正好连接两个房间。房间编号从 $1$ 到 $n$。宫殿只有一个入口，通向编号为 $1$ 的房间。对于每个房间，从入口到它只有一条不回头的路线。换句话说，房间和走廊形成了一棵树——一个连通无环图。 负责批准建筑的消防员要求在内部放置灭火器。 他的具体要求如下： - 灭火器应放置在（某些）房间中，一个房间可以存放任意数量的灭火器。 - 每个房间必须分配一个灭火器，尽管它可以存放在另一个房间中。 - 每个灭火器最多可以分配给 $s$ 个不同的房间。 - 对于每个房间，其分配的灭火器在 $k$ 条走廊范围内。 Byteasar 对奢华的宫殿情有独钟，所以毫不奇怪，在完成另一个辉煌的宫殿后，他现在几乎没有钱。 因此，他对满足消防员要求所需的最少灭火器数量感兴趣。

标准输入的第一行包含三个整数 $n$、$s$ 和 $k$，用单个空格分隔，$1 \le n \le 10^5$，$1 \le s \le n$，$1 \le k \le 20$。 接下来的 $n-1$ 行中的每一行包含两个整数，用单个空格分隔。 第 $i+1$ 行包含数字 $x_i,y_i$，表示连接房间编号 $x_i$ 和 $y_i$ 的走廊。

标准输出的第一行应包含一个整数——在宫殿中必须安装的最少灭火器数量。

$1 \leq n,s \leq 100000, 1 \leq k \leq 20 , x_i \geq 1$。 题面翻译由 ChatGPT-4o 提供。