[关闭]
@ysner 2018-10-09T22:56:07.000000Z 字数 1318 阅读 1865

luogu3942将军令

贪心 树形DP DP


题面

在大小为的树上选择尽量少的点,使得所有未选择的点距离选择了的点小于等于

解析

为正整数。
为距离最近的,选择了的点,还能向上覆盖的距离为。这类标记称为
为距离最近的,选择了的点,的覆盖范围为。这类标记陈伟
(主要是为了避免的两重含义)
给所有叶结点打这个标记。
向上汇集标记时,如果,说明点可以被下面的某个选择了的点覆盖到,取标记。
否则取标记。
同时如果,这个点必须被选择(否则就有点覆盖不到)。

特别注意根结点。
如果到根时标记为负数,根需要单独放个标记(因为没有点在更上面覆盖它了)。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=1e5+100;
  14. int n,k,t,f[N],g[N],h[N],cnt;
  15. struct Edge{int to,nxt;}e[N<<1];
  16. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  17. il int gi()
  18. {
  19. re int x=0,t=1;
  20. re char ch=getchar();
  21. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  22. if(ch=='-') t=-1,ch=getchar();
  23. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  24. return x*t;
  25. }
  26. il void dfs(re int u,re int fa)
  27. {
  28. re int mor=0,les=-1,son=0;
  29. for(re int i=h[u];i+1;i=e[i].nxt)
  30. {
  31. re int v=e[i].to;
  32. if(v==fa) continue;++son;
  33. dfs(v,u);
  34. g[u]+=g[v];
  35. --f[v];if(!f[v]) --f[v];
  36. if(f[v]>0) mor=max(mor,f[v]);
  37. else les=min(les,f[v]);
  38. }
  39. if(abs(mor)>=abs(les)) f[u]=mor;
  40. else if(les<=-k-1||u==1) f[u]=k+1,++g[u];
  41. else f[u]=les;
  42. }
  43. int main()
  44. {
  45. memset(h,-1,sizeof(h));
  46. n=gi();k=gi();gi();
  47. fp(i,1,n-1)
  48. {
  49. re int u=gi(),v=gi();
  50. add(u,v);add(v,u);
  51. }
  52. dfs(1,0);
  53. printf("%d\n",g[1]);
  54. return 0;
  55. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注