初始数组忘了赋初值，，，我真是个机灵鬼
还有这题是三倍经验&&，这题的实现思想来自P2279首个题解
简化题意
给你一棵树，你有一些可以覆盖范围为$k$的障碍物，问最少放几个障碍物可以使树上所有节点覆盖
思想
这题贪心的思路其他题解写的十分清楚。首先，每一次选的点不和之前选的点所覆盖的区间重合，否则不优（这点很显然），所以我们每次可以找到一个最低的点，选取它的第K级祖先来覆盖这个点。$ta$和$ta$的祖先之间就标记为已覆盖
代码实现讲解
实现难点在判断该点是否被覆盖，每个点被覆盖的情况有三种
- 被自己的孩子所覆盖
- 此时直接在$ta$的孩子建立时就标记
- 被自己的祖先所覆盖
- 开一个数组${fa[]}$去记录
- 被自己的兄弟所覆盖
- 开一个数组${dis[i]}$表示离$i$最近的障碍物离$i$的距离，当${dis[fa[i]]==k-1}$时，我们就可以确定，$i$肯定就会被覆盖
每次在放置完障碍物之后，还要记得更新${dis[]}$的值
顺便一提，这种方法的普适性很强，可以解决半径为k的最小覆盖问题。而且不用存图。只需要把维护“父亲和爷爷”改成维护“上位k位祖先”即可，复杂度O(N*K)，常数也很小。————
这题的代码实现就是这句话的延申
代码实现
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int maxn=1e6+10; 7 struct ziji{ int id,dep;}mn[maxn]; 8 #define id(i) mn[i].id 9 #define dep(i) mn[i].dep10 int n,k,t,fa[maxn],dis[maxn],ans,tot;11 int head[maxn],ver[maxn<<1],nxt[maxn<<1];12 inline bool cmp(ziji a,ziji b){13 return a.dep>b.dep;14 }15 inline int g() { register int x=0,f=1;16 register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;17 do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;18 } 19 inline void add(int x,int y){20 ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;21 }22 inline void dfs(int x,int f){23 dep(x)=dep(f)+1;fa[x]=f;24 for(register int i=head[x];i;i=nxt[i]){25 int y=ver[i];if(y==f) continue;dfs(y,x);26 }27 }28 int main(){29 n=g(),k=g(),t=g();30 id(1)=1,dis[0]=dis[1]=maxn;31 for(register int i=1;i<=n;i++) id(i)=i;32 memset(dis,0x3f,sizeof(dis));33 for(register int i=2;i<=n;i++){34 int x,y;x=g(),y=g();35 add(x,y),add(y,x);36 }dfs(1,1);37 sort(mn+1,mn+1+n,cmp);38 for(register int i=1;i<=n;i++){39 int x=id(i),y=x;40 for(register int j=1;j<=k;j++)41 y=fa[y],dis[x]=min(dis[x],dis[y]+j);42 if(dis[x]>k){43 dis[y]=0,ans++;44 for(register int j=1;j<=k;j++)45 y=fa[y],dis[y]=min(dis[y],j);46 }47 }48 printf("%d",ans);49 }