初始数组忘了赋初值，，，我真是个机灵鬼
还有这题是三倍经验P2279&&P2016，这题的实现思想来自P2279首个题解
luogu
简化题意
给你一棵树，你有一些可以覆盖范围为$k$的障碍物，问最少放几个障碍物可以使树上所有节点覆盖
思想
这题贪心的思路其他题解写的十分清楚。首先，每一次选的点不和之前选的点所覆盖的区间重合，否则不优（这点很显然），所以我们每次可以找到一个最低的点，选取它的第K级祖先来覆盖这个点。$ta$和$ta$的祖先之间就标记为已覆盖
代码实现讲解
实现难点在判断该点是否被覆盖，每个点被覆盖的情况有三种
- 被自己的孩子所覆盖
- 此时直接在$ta$的孩子建立时就标记
- 被自己的祖先所覆盖
- 开一个数组${fa[]}$去记录
- 被自己的兄弟所覆盖
- 开一个数组${dis[i]}$表示离$i$最近的障碍物离$i$的距离，当${dis[fa[i]]==k-1}$时，我们就可以确定，$i$肯定就会被覆盖
每次在放置完障碍物之后，还要记得更新${dis[]}$的值
这题的代码实现就是这句话的延申
代码实现
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 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].dep 10 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 }