⼩w⼼⾥的⽕焰就要被熄灭了。简便起⻅，假设⼩w的内⼼是⼀棵n−1条边，n个节点的树。现在你要在每个节点⾥放⼀些个灭⽕器，每个节点可以放任意多个。接下来每个节点都要被分配给⼀个⾄多k条边远的灭⽕器，每个灭⽕器最多能分配给s个节点。⾄少要多少个灭⽕器才能让⼩w彻底死⼼呢？
题解
树形DP，由于k≤20k\le20k≤20，用f[i][j]f[i][j]f[i][j]存iii这个点下面距离为jjj的未匹配点有多少个，g[i][j]g[i][j]g[i][j]存iii下面能够再往上拓展jjj长度的灭火器分配数量（一个灭火器提供sss的数量）。那么根据贪心，肯定是f[i][k]f[i][k]f[i][k]必须在iii处放灭火器，然后剩下的能配就配，因为如果可以，在下面配显然更优。
时间复杂度O(nk)O(nk)O(nk)。
CODE#include<bits/stdc++.h>usingnamespacestd;inlinevoidrd(int&x){charch;while(!isdigit(ch=getchar()));for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');}constintMAXN=100005;constintMAXK=25;intn,s,k,ans;intfir[MAXN],to[MAXN<<1],nxt[MAXN<<1],cnt;inlinevoidlink(intu,intv){to[++cnt]=v;nxt[cnt]=fir[u];fir[u]=cnt;to[++cnt]=u;nxt[cnt]=fir[v];fir[v]=cnt;}intf[MAXN][MAXK],g[MAXN][MAXK];voiddfs(intu,intff){for(inti=fir[u],v;i;i=nxt[i])if((v=to[i])!=ff){dfs(v,u);for(intj=0;j<k;++j)f[u][j+1]+=f[v][j];for(intj=1;j<=k;++j)g[u][j-1]+=g[v][j],g[u][j-1]=min(g[u][j-1],n);//此处g可能加爆int我就因为这里考试爆了10分(没能akQAQ)}++f[u][0];if(f[u][k]){intneed=(f[u][k]+s-1)/s;ans+=need;g[u][k]+=min(1ll*need*s,1ll*n)-f[u][k];f[u][k]=0;}inttmp,cur=k;for(inti=k;i>=0;--i){while(f[u][i]&&cur>=i){tmp=min(f[u][i],g[u][cur]);f[u][i]-=tmp,g[u][cur]-=tmp;if(!g[u][cur])--cur;}}}intmain(){rd(n),rd(s),rd(k);for(inti=1,u,v;i<n;++i)rd(u),rd(v),link(u,v);dfs(1,0);intsum=0;for(inti=0;i<=k;++i)sum+=f[1][i];printf("%d\n",ans+(sum+s-1)/s);}
