P3523 [POI2011]DYN-Dynamite

这道题乍一看非常毒瘤~~（其实我连题都没看懂）~~ 看到最大值最小，可以想到二分答案 我们直接二分出题目所求的“关键节点到这些点中距离的最小值的最大值” 然后题意转化成为：已知一个点可以覆盖的范围，判断能否用不超过m个点覆盖整棵树 那么如何check二分的答案呢？ 可以用贪心解决~~（虽然我也是看了题解）~~ 从1号节点开始dfs，直到当前节点k与关键节点的距离达到mid，就把k选中 贪心的正确性是比较显然的： 如果在k的子树中选择了节点，则其向上能覆盖的范围一定不会超过k的覆盖范围 楼下Kelin大佬讲得非常详细~~（太强了）~~ 丑陋的代码： ```cpp #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; const int N=3e5+5; struct edge { int to,nxt; }edge[N<<1]; int n,m,num,t,tot,f[N],fa[N],cnt[N],head[N]; bool ex[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to) { edge[++num].nxt=head[from]; edge[num].to=to; head[from]=num; } void dfs(int k)//已知覆盖范围，用最少的点覆盖整棵树（从下向上贪心，必须选才选） { int tmp1=ex[k]?0:-1e7,tmp2=-1e7; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (v==fa[k]) continue; fa[v]=k; dfs(v); if (cnt[v]==1) tmp1=max(tmp1,f[v]+1); if (cnt[v]==2) tmp2=max(tmp2,f[v]-1); } if (tmp1>tmp2) if (tmp1==t) ++tot,cnt[k]=2,f[k]=t; else cnt[k]=1,f[k]=tmp1; else cnt[k]=2,f[k]=tmp2; } inline bool check(int k)//即一个选择点能覆盖的范围 { t=k; tot=0; dfs(1); if (f[1]>=0&&cnt[1]==1) ++tot; return tot<=m; } int main() { n=read(),m=read(); for (reg int i=1;i<=n;ex[i++]=read()); for (reg int i=1;i<n;i++) { int x=read(),y=read(); add_edge(x,y); add_edge(y,x); } int l=0,r=n,ans=0; while (l<=r) { int mid=(l+r)>>1;//关键点与选择点之间距离最小值的最大值 if (check(mid)) { ans=mid; r=mid-1; } else l=mid+1; } printf("%d\n",ans); return 0; } ```