题目描述

题目译自 XVI OI Olimpiada Informatyczna – I etap Gaśnice

Bajtazar 斥资兴建了一座新宫殿。这座宫殿由 $n$ 个房间和连接它们的 $n-1$ 条走廊组成，房间编号从 $1$ 到 $n$，入口位于房间 $1$。每条走廊连接两个不同房间，从入口到每个房间有且仅有一条路径（无回退）。换言之，房间和走廊构成一棵树——一个连通的无环图。

消防督察在验收宫殿时，要求安装灭火器，并提出以下规定：

• 灭火器需放置在某些房间内，每个房间可放置多台灭火器。
• 每个房间需指定一台特定的灭火器。
• 每台灭火器最多为 $s$ 个房间提供灭火服务。
• 从任意房间到其指定灭火器的路径，最多经过 $k$ 条走廊。

Bajtazar 建完宫殿后囊中羞涩，急需精打细算。他想知道，满足上述要求的最少灭火器数量是多少？请编写程序，帮他解决这一难题。

输入格式

第一行包含三个整数 $n, s, k$ $(1 \leq n \leq 100000, 1 \leq s \leq n, 1 \leq k \leq 20)$，分别表示房间数、每台灭火器最多服务的房间数、以及从房间到灭火器的最大走廊数。

接下来的 $n-1$ 行，每行包含两个整数 $x_i, y_i$ $(1 \leq x_i < y_i \leq n)$，表示连接房间 $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