【jzoj5360】【NOIP2017提高A组模拟9.12】【Shorten Diameter】

description

给定一棵有n 个点的树，现要求不断删点直到树的直径<=K，求最少需要删除的点数。

一个点可以被删掉当且仅当该点的度数为1。

保证树的形态为随机生成（请勿过度解读）。

solution

由于树的形态是随机的，可以考虑当k为偶数时，枚举一个点往外扩展k/2层，当k为奇数时，枚举一条边从两个点往外扩展k/2层，统计最大值即可。

code

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define ULL unsigned int
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int const mn=2*1e3+3,mo=1e9+7;
int n,K,tmp,u[mn],v[mn],gra,begin[mn],to[mn*2],next[mn*2];
void insert(int u,int v){
to[++gra]=v;
next[gra]=begin[u];
begin[u]=gra;
}
void dfs(int p,int q,int dep){
tmp++;
if(!dep)return;
fr(i,p)if(to[i]!=q)
dfs(to[i],p,dep-1);
}
int main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d%d",&n,&K);
fo(i,1,n-1){
scanf("%d%d",&u[i],&v[i]);
insert(u[i],v[i]);
insert(v[i],u[i]);
}
int ans=0;
if(K&1){
fo(i,1,n-1){
tmp=0;
dfs(u[i],v[i],K/2);
dfs(v[i],u[i],K/2);
ans=max(ans,tmp);
}
}else{
fo(i,1,n){
tmp=0;
dfs(i,0,K/2);
ans=max(ans,tmp);
}
}
printf("%d",n-ans);
return 0;
}

最后

以上就是难过乌龟为你收集整理的【jzoj5360】【NOIP2017提高A组模拟9.12】【Shorten Diameter】的全部内容，希望文章能够帮你解决【jzoj5360】【NOIP2017提高A组模拟9.12】【Shorten Diameter】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。