Description：

一棵树，每个点至少被一个灭火器覆盖，每个灭火器可以最多覆盖 $s$ 个点，灭火器最远可以覆盖距离为 $k$ 的点，求出最少需要放置多少灭火器。

$1\leqslant n\leqslant 10^5,1\leqslant k\leqslant 20$

Solution：

看上去和 POI2011 Dynamite 很像，实际上思想是十分类似的，都是树上贪心，只是这个有了个数的限制，但发现 $k$ 只有 $20$ ，所以可以把它记到树形 $DP$ 的状态里，类似侦察守卫的做法，设 $f[k][w]$ 表示在 $k$ 点长为 $w$ 的总共还能再覆盖几个， $g[k][w]$ 表示在 $k$ 点长为 $w$ 的总共还缺几个，这样统计十分简单，如果 $g[k][m]$ 不为 $0$ ，也就是说不得不在这里放，那就放 $\lceil\frac{g[k][m]}s\rceil$ 个，重点在于怎么合并 $f[][]$ 和 $g[][]$ ，我们肯定尽量不浪费任何距离，也就是说如果 $m+1\leqslant i+j\leqslant m$ 的话，那他们在之后一层不能再合并，因为距离超了，所以就在这一层合并，否则把它留上去不会变差。注意根节点的特殊情况。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,s,m;

#define MAXN 100010

#define MAXM 21

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

long long f[MAXN][MAXM];

long long g[MAXN][MAXM];

int ans = 0;

bool v[MAXN];

void dp(int k)

{

	g[k][0] = 1;

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp(e[i].to);

		for(int w = 0;w < m;++w)f[k][w] += f[e[i].to][w + 1];

		for(int w = 1;w <= m;++w)g[k][w] += g[e[i].to][w - 1];

	}

	if(g[k][m] != 0)

	{

		int tmp = (g[k][m] + s - 1) / s;

		f[k][m] = tmp * s - g[k][m];

		g[k][m] = 0;

		ans += tmp;

	}

	for(int i = 0;i <= m;++i)

	{

		for(int j = i;j >= 0 && (j >= i - 1 || k == 1);--j)

		{

			if(f[k][i] >= g[k][j])

			{

				f[k][i] -= g[k][j];

				g[k][j] = 0;

			}

			else

			{

				g[k][j] -= f[k][i];

				f[k][i] = 0;

			}

		}

	}

	return;

}

int main()

{

	scanf("%d%d%d",&n,&s,&m);

	for(int i = 1;i < n;++i)add(read(),read());

	dp(1);

	long long rem = 0;

	for(int i = 0;i <= m;++i)

	{

	    rem += g[1][i];

	}

	cout << ans + (rem + s - 1) / s << endl;

	return 0;

}