这题似乎可以纯模拟？？？

思路

注意到$n\leq 2000$，再一次感谢出题人大大手下留情，似乎可以$O(N^2)$。考虑两种情况： 1.当$k$为奇数时，枚举树的中心，在强行遍历一遍树，记录下每一个点的深度，完事后枚举每一个点，如果它的深度$< k/2$肯定是可以选的，最终记录答案即可。 2.当$k$为偶数时，转而枚举每一条边，以它的起点为根节点遍历整个树，每一个$dep \leq k/2$的节点都可以保留，记录一下，在从这条边的重点开始遍历，每一个$dep \leq k/2$的节点也可以保留，最终用或运算计算答案，记录即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=2100;
vector<int>G[N];
int n,k,dep[N],vis[N];
void dfs(int x,int fa)
{
	for(int i:G[x])if(i!=fa)dep[i]=dep[x]+1,dfs(i,x);
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
	int ans=0;
	if(k%2==0)
	{
		for(int r=1;r<=n;r++)
		{
			memset(dep,0,sizeof(dep));
			dep[r]=0;dfs(r,0);
			int cnt=0;
			for(int i=1;i<=n;i++)if(dep[i]<=k/2)cnt++;
			ans=max(ans,cnt);
		}
	}
	else
	{
		for(int x=1;x<=n;x++)for(int y:G[x])if(x<y)
		{
			memset(dep,0,sizeof(dep));memset(vis,0,sizeof(vis));
			dep[x]=0;dfs(x,0);
			for(int i=1;i<=n;i++)if(dep[i]<=k/2)vis[i]=1;
			dep[y]=0;dfs(y,0);
			int cnt=0;
			for(int i=1;i<=n;i++)if(vis[i]||dep[i]<=k/2)cnt++;
			ans=max(ans,cnt);
		}
	}
	printf("%d\n",n-ans);
	return 0;
}

冷知识:阎帝赛后刚好想出来解法,只能回家写题

D51 树的直径 [AGC001C] Shorten Diameter

// 树的直径+逆向思维
#include<bits/stdc++.h>
using namespace std;

#define N 2005
int h[N],to[N<<1],ne[N<<1],idx;
void add(int x,int y){
  to[++idx]=y;ne[idx]=h[x];h[x]=idx;
}
int n,k,tot,ans;

void dfs(int x,int fa,int step){
  tot++; //记录节点数
  if(step==0) return;
  for(int i=h[x];i;i=ne[i]){
    int y=to[i];
    if(y!=fa) dfs(y,x,step-1);
  }
}
int main(){
  scanf("%d%d",&n,&k);
  for(int i=1,u,v;i<n;i++){
    scanf("%d%d",&u,&v);
    add(u,v);add(v,u);
  }
  if(k%2==0){ //k为偶数
    for(int x=1;x<=n;x++){
      tot=0;
      dfs(x,0,k/2); //以x为中心扩展
      ans=max(ans,tot);
    }
  }
  else{ //k为奇数
    for(int x=1;x<=n;x++){
      for(int i=h[x];i;i=ne[i]){
        tot=0;
        int y=to[i];
        dfs(y,x,k/2);
        dfs(x,y,k/2); //以x,y为中心扩展
        ans=max(ans,tot);
      }
    }
  }
  printf("%d\n",n-ans);
}

这题似乎可以纯背包？？？

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
vector<int>G[N];
int dp[N][N],mx[N],mx1[N],n,k,ans;
void dfs(int x,int f)
{
	dp[x][0]=0;
	for(int y:G[x])if(y!=f)
	{
		dfs(y,x);
		mx[0]=dp[x][0];for(int i=1;i<=n;i++)mx[i]=max(mx[i-1],dp[x][i]);
		for(int i=1;i<=k;i++)mx1[i]=max(mx1[i-1],dp[y][i-1]);
		for(int i=1;i<=k;i++)
			dp[x][i]=max(dp[x][i]+mx1[min(i,k-i)],mx[min(i,k-i)]+dp[y][i-1]);
	}
	for(int i=0;i<=k;i++)dp[x][i]++;
	for(int i=0;i<=k;i++)ans=max(ans,dp[x][i]);
}
signed main()
{
	cin>>n>>k;
	for(int i=1;i<n;i++)
	{
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0);
	cout<<n-ans;
	return 0;
}