自动搬运

查看原文

来自洛谷，原作者为

	BJpers2 **

搬运于2025-08-24 21:35:53，当前版本为作者最后更新于2018-05-31 20:00:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看大家写的DP好强...我这里就提供一种比较简洁的贪心吧。

其实贪心思想楼上都已经说的很清楚了，就是找最低没被覆盖到的点，并在它的祖父处设一个消防站。考虑到这个点的所有子孙后代都已经被覆盖了，因此这时覆盖祖父能盖到更多额外的点，并保证结果不会更差。

很多思路是用dfs或堆求取最低节点，实际上没必要，只要预处理出深度（边输入边处理）并排序，碰到已覆盖就跳过，未覆盖就在祖父处设消防站，ans++。

问题在于怎样才能判断这个点覆盖到了没有。对于儿子或孙子覆盖他，可以在在儿子处设站时就标记它；而对于父亲和祖父覆盖他，可以用儿子对父亲的映射f来解决；问题在于兄弟。其实，可以用o数组维护“离i最近的消防站到i的距离”，当o[父亲]==1时，就能确定它是否被覆盖。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 2020
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,b[N],f[N],d[N],o[N],ans,u,v,w;
bool cmp(int x,int y){return d[x]>d[y];}
int main(){
	scanf("%d",&n);b[1]=1,o[1]=o[0]=N;
	FOR(i,2,n) scanf("%d",&f[i]),d[i]=d[f[i]]+1,b[i]=i,o[i]=N;
	sort(b+1,b+n+1,cmp);
	FOR(i,1,n){
		v=b[i],w=f[v],u=f[f[v]];
		o[v]=min(o[v],min(o[w]+1,o[u]+2));
		if(o[v]>2){
			o[u]=0,ans++;
			o[f[u]]=min(o[f[u]],1),o[f[f[u]]]=min(o[f[f[u]]],2);
		}
	}printf("%d",ans);
}

顺便一提，这种方法的普适性很强，可以解决半径为k的最小覆盖问题。而且不用存图。只需要把维护“父亲和爷爷”改成维护“上位k位祖先”即可，复杂度O(N*K)，常数也很小。