AGC 001 C - Shorten Diameter

题意

给你一棵树
要你删掉最少的点，使得剩下的直径不超过$k$

题解

感觉被官方题解打爆了啊
成为弱智选手

先说官方题解
不妨枚举直径的中点，那么dfs一下，删掉所有深度大于k/2的就可以了
如果k是奇数，那么中点就在边上，枚举边即可

但是不知道为什么没有想到这个做法，居然没有去想枚举中点

考虑DP
$f_{i,j}$表示i这个子树里面，最长链为$j$的最优答案
似乎直接转移就可以了
枚举到子树大小就$O(nk)$的了

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int N=2005;
int n,k;
vector<int> vec[N];
int f[N][N];
int tmp[N];
int tot[N];
int ans=0;
void dfs (int x,int fa)
{
    f[x][0]=1;tot[x]=1;int siz=vec[x].size();for (int u=0;u<siz;u++){
    int y=vec[x][u];if (y==fa) continue;dfs(y,x);for (int i=0;i<=k;i++) tmp[i]=0;for (int i=0;i<=min(tot[x],k);i++)for (int j=0;j<=min(tot[y],k-1);j++){
    int l=i+j+1;if (l>k) break;tmp[max(i,j+1)]=max(tmp[max(i,j+1)],f[x][i]+f[y][j]);}for (int i=0;i<=k;i++) f[x][i]=max(f[x][i],tmp[i]);tot[x]+=tot[y];}//printf("x:%d\n",x);for (int i=0;i<=k;i++) {
    // printf("%d ",f[x][i]);ans=max(ans,f[x][i]);}//printf("\n");
}
int main()
{
    scanf("%d%d",&n,&k);for (int u=1;u<n;u++){
    int x,y;scanf("%d%d",&x,&y);vec[x].push_back(y);vec[y].push_back(x);}dfs(1,0);printf("%d\n",n-ans);return 0;
}