• 应用
• 登录
• 注册

# P3479 [POI2009]GAS-Fire Extinguishers

• 83通过
• 197提交
• 题目提供者 jjikkollp
• 评测方式 云端评测
• 标签 贪心 POI 2009 高性能
• 难度 省选/NOI-
• 时空限制 1000ms / 128MB
• 提示：收藏到任务计划后，可在首页查看。

## 题目描述

Byteasar has had a new palace built.

It consists of chambers and corridors connecting them. Each corridor connects exactly two chambers.

The rooms are numbered from to .

There is only a single entrance to the palace, which leads to chamber no. .

For each chamber there is exactly one route leading to it from the entrance, without turning back on the way.

In other words, the chambers and the corridors form a tree - a connected acyclic graph.

The fire marshal who is to approve the building demands placing fire extinguishers inside.

The following are his exact requirements:

The fire extinguishers should be placed in (some) chambers, and one chamber may store any number of extinguishers.

Each chamber has to be assigned one fire extinguisher, though it may be stored in another chamber.

Each fire extinguisher can be assigned to at most different chambers.

For each room its assigned extinguisher is within the range of corridors.

Byteasar has a week spot for lavish palaces, so it is no surprise he has very little money now, right after completion of another splendid palace.

Therefore he is interested in the minimum number of fire extinguishers sufficient for satisfying fire marshal's demands.

Byteasar建好了一个宫殿。

这个宫殿有n个房间，由n-1条走廊连接，每一个走廊连接两个房间。

房间编号由1到n ，整个宫殿只有一个入口，对于每个房间都有一条唯一的路径到达。

换句话说，这是一棵树

接下来要在这棵树上放灭火器，并遵循以下规则：

1.每个点至少需要被一个灭火器覆盖，但这个灭火器不一定在这个点上

2.每个灭火器可以最多覆盖s个不同的点

3.每个灭火器最远可以覆盖距离为k的点

现在Byteasar很穷，所以让你求出最少需要放置多少灭火器。

## 输入输出格式

输入格式：

The first line of the standard input contains three integers , and separated by single spaces, , , .

Each of the following lines holds two integers separated by a single space.

Line no. contains the numbers denoting the corridor connecting chambers no. and .

第一行三个整数，n,m,k 如题目描述所示。

接下来n-1每行给出两个整数x,y，表示x,y两个房间有走廊相连。

输出格式：

The first and only line of the standard output is to hold one integer - the minimum number of fire extinguishers that have to be installed in palace.

一行一个正整数，表示最少放置的灭火器数量。

## 输入输出样例

输入样例#1： 复制
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

输出样例#1： 复制
4


## 说明

$1\leq n,m\leq 100000, 1\leq k \leq 20 , x_i\geq1$

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。