洛谷数据非常水，建议去bzoj
我第一眼一看这不是那个POI2011的升级版吗(明明这个是2009年的，应该说那个是这个的弱化版，果然思想差不多。
因为$k$很小，可以考虑每个间隔距离来转移。我们按照传统(雾，其实这里的的名字已经不是很符合定义了，设$cov[i][j]$表示以$i$为根的子树里剩余控制距离为$j$的点还能控制几个点，$unc[i][j]$表示以$i$为根的子树里还没被覆盖的距离等于$j$的点有几个。每次从儿子获取信息后先更新$cov[x][k]$，然后就是这“类”题的关键：$cov$和$unc$这两个数组如何互相抵消。
考虑贪心，对于除了根节点以外的点，我们只让它的$cov[i][j]$去和$unc[i][j-1]$和$unc[i][j]$抵消，也就是只和过了这个点就抵消不了的抵消。可能你会问为什么要抵消距离为$j-1$的点(看起来它们是可以交给父亲抵消的)，这是因为我们再往上走一步会导致控制距离减一，实际距离加一，这样一来其实是抵消不了的。
注意在根节点还要把剩下的没抵消掉的抵消.......
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,K=;
int p[N],noww[*N],goal[*N];
long long cov[N][K],unc[N][K];
long long s,k,cst,ans;
int n,t1,t2,cnt;
void link(int f,int t)
{
noww[++cnt]=p[f];
goal[cnt]=t,p[f]=cnt;
}
void DFS(int nde,int fth)
{
unc[nde][]=;
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth)
{
DFS(goal[i],nde);
for(int j=;j<=k;j++)
{
unc[nde][j]+=unc[goal[i]][j-];
cov[nde][k-j]+=cov[goal[i]][k-j+];
}
}
long long tmp=(unc[nde][k]+s-)/s;
ans+=tmp,cov[nde][k]+=tmp*s;
for(int i=;i<=k;i++)
if(cov[nde][i])
{
for(int j=i;~j;j--)
if(i-j<=||nde==)
{
if(cov[nde][i]<=unc[nde][j])
{
unc[nde][j]-=cov[nde][i];
cov[nde][i]=; break;
}
cov[nde][i]-=unc[nde][j],unc[nde][j]=;
}
else break;
}
}
int main ()
{
scanf("%d%lld%lld",&n,&s,&k);
for(int i=;i<n;i++)
{
scanf("%d%d",&t1,&t2);
link(t1,t2),link(t2,t1);
}
DFS(,);
for(int i=;i<=k;i++)
cst+=unc[][i];
printf("%lld",ans+(cst+s-)/s);
return ;
}