[PHP知识库]问题 M: Shorten Diameter

http://icpc.upc.edu.cn/problem.php?cid=2919&pid=12

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>g[2003];
int cnt;
int dep[2003];
int n,k;
void dfs(int now,int fa,int gap)
{
    for(int i=0; i<g[now].size(); i++)
    {
        int next=g[now][i];
        if(next==fa) continue;
        dep[next]=dep[now]+1;
        if(dep[next]>gap) cnt++;
        dfs(next,now,gap);
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<n; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans=0x3F3F3F3F;
    if(k%2==0)///如果k是偶数，那么距离这个点大于（k/2）的点都删去
    {
        for(int i=1; i<=n; i++)
        {
            cnt=0;
            dep[i]=0;
            dfs(i,0,k/2);
            ans=min(ans,cnt);
        }
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
          for(int j=0;j<g[i].size();j++)
          {
              cnt=0;
              dep[i]=0;
              dfs(i,g[i][j],(k-1)/2);
              dep[g[i][j]]=0;
              dfs(g[i][j],i,(k-1)/2);
              ans=min(ans,cnt);
          }
        }
    }
    printf("%d\n",ans);
    return 0;
}