这是以前的经典题目的难化版本。。 一开始以为要dp，列了很多方程感觉都不合适= =结果发现是贪心QAQ。 我们对于每个点维护两个东西。 以x为根的子树中距离这个点为i的点需要被覆盖多少个 以x为根的子树中距离这个点为i的点还能被覆盖多少个。
转移显然。 那么一种很明显的贪心策略就是能放就放。。如果需要的>能覆盖的明显就需要放一些在这个点上。 问题是怎么抵消两个量呢。 贴commonc大神的解释：
我们知道当我们用一个剩余覆盖范围很广的消防站去覆盖一个离的很近的消防站显然是浪费 所以我们抵消的原则是：再过一步就抵消不了了的时候，我们才去抵消 也就是说，若这个消防站控制范围为i，我们只去抵消距离为i和i-1的节点 #include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e5+5; int fa[N]; typedef long long ll; int n,S,K; ll cover[N][21],remain[N][21],ans; int go[N<<1],tot,next[N<<1],head[N<<1]; inline void add(int x,int y) { go[++tot]=y; next[tot]=head[x]; head[x]=tot; } inline void build(int x) { cover[x][0]=1; for(int i=head[x];i;i=next[i]) { int v=go[i]; if (v==fa[x])continue; fa[v]=x;build(v); fo(k,0,K-1)cover[x][k+1]+=cover[v][k]; fd(k,K,1)remain[x][k-1]+=remain[v][k]; } int k=(cover[x][K]+S-1)/S;//多出来的S-1表示任意一个多出来的点都不能丢掉 ans+=k; remain[x][K]+=k*S; fo(j,0,K) if (remain[x][j]) { for(int k=j;k>=0&&(k>=j-1||x==1);k--) { if (remain[x][j]<=cover[x][k]) { cover[x][k]-=remain[x][j]; remain[x][j]=0; break; } remain[x][j]-=cover[x][k]; cover[x][k]=0; } } } int main() { scanf("%d%d%d",&n,&S,&K); fo(i,1,n-1) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } build(1); int tot=0; fo(i,0,K)tot+=cover[1][i]; ans+=(tot+S-1)/S; printf("%lld\n",ans); }