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

发布时间：2024-11-12 05:10

Description

给定一棵有n 个点的树，现要求不断删点直到树的直径<=K，求最少需要删除的点数。
一个点可以被删掉当且仅当该点的度数为1。

Input

第一行两个数n，k，意义如题所述。
接下来n -1 行描述这棵树。

Output

一个数表示答案。

Sample Input

6 2
1 2
3 2
4 2
1 6
5 6

Sample Output

题解

最后保留下来的树的直径是不超过k的，
但如果是最优的情况，就尽快取到k。

我们枚举一个一定被保留的点，
先看k是偶数的情况，那么从这个点向外延伸k/2条边的都可以保留下来，
这样两边加起来就是直径k了。

如果k是奇数，对于一个点i，它的所以儿子中，只能有一个儿子向外延伸k/2+1条边，
其余的儿子都只能是k/2条边。
因为如果存在两个儿子都选了k/2+1条边，那么最终的直径就是k+1了。

code

#include<queue> #include<cstdio> #include<iostream> #include<algorithm> #include <cstring> #include <string.h> #include <cmath> #include <math.h> #define ll long long #define N 2003 #define db double #define P putchar #define G getchar #define mo 10000 using namespace std; char ch; void read(int &n) { n=0; ch=G(); while((ch<'0' || ch>'9') && ch!='-')ch=G(); ll w=1; if(ch=='-')w=-1,ch=G(); while('0'<=ch && ch<='9')n=n*10+ch-'0',ch=G(); n*=w; } int max(int a,int b){return a>b?a:b;} int min(int a,int b){return a<b?a:b;} void write(int x) { if(x>9) write(x/10); P(x%10+'0'); } int next[N*2],a[N*2],b[N],tot; int n,ans,sum,mx,k,x,y,son[N]; void ins(int x,int y) { next[++tot]=b[x]; a[tot]=y; b[x]=tot; } int dfs(int x,int fa,int deep) { if(deep==0)return 0; int s=1; for(int i=b[x];i;i=next[i]) if(a[i]!=fa)s+=dfs(a[i],x,deep-1); return s; } int main() { freopen("c.in","r",stdin); freopen("c.out","w",stdout); read(n);read(k); for(int i=1;i<n;i++) read(x),read(y),ins(x,y),ins(y,x); for(int i=1;i<=n;i++) { mx=0; sum=1; for(int j=b[i];j;j=next[j]) { x=dfs(a[j],i,k/2); y=dfs(a[j],i,k/2+1); sum+=x; mx=max(mx,y-x); } if(k%2)sum+=mx; ans=max(ans,sum); //write(sum),P(' '),write(mx),P('\n'); } write(n-ans); }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182

网址：JZOJ5360. 【NOIP2017提高A组模拟9.12】Shorten Diameter https://www.yuejiaxmz.com/news/view/46082

上一篇: 小明在探究“斜面的机械效率”的实

下一篇: 学习=输入+输出