f[x][0] 表示最近控制驿站的距离
f[x][1]表示最远不能控制的驿站距离
当f[x][0]+f[x][1]≤k是说明能被控制，但没有贡献
当f[x][1]=k时，x必须被控制，这时已经到达能控制点的最远距离，如果再向上，x就无法被控制
正确性：如果x可以向上移动，并且仍然能控制x移动前能控制的点，就把x向上移动，这样不会变差的
code
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define ll long long 5 const int maxn=1e5+10; 6 const int inf=1e9+7; 7 inline int read(){ 8 int x=0,f=1; 9 char c=getchar(); 10 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 11 while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();} 12 return x*f; 13 } 14 int n,k,t,ans; 15 struct edge{ 16 int nxt,to; 17 }e[maxn*2]; 18 int head[maxn],cnt,f[maxn][2]; 19 inline void add(int from,int to){ 20 e[++cnt].to=to;e[cnt].nxt=head[from];head[from]=cnt; 21 } 22 void dfs(int x,int fa){ 23 f[x][0]=inf;f[x][1]=0; 24 for(int i=head[x];i;i=e[i].nxt){ 25 int y=e[i].to; 26 if(y==fa)continue; 27 dfs(y,x); 28 if(~f[y][1]){ 29 f[x][1]=max(f[x][1],f[y][1]+1); 30 } 31 f[x][0]=min(f[x][0],f[y][0]+1); 32 } 33 if(f[x][1]==k){ 34 ans++; 35 f[x][0]=0;f[x][1]=-1; 36 } 37 if(f[x][1]+f[x][0]<=k)f[x][1]=-1; 38 } 39 int main(){ 40 n=read();k=read();t=read(); 41 for(int i=1;i<n;i++){ 42 int x,y;x=read();y=read(); 43 add(x,y);add(y,x); 44 } 45 dfs(1,0); 46 if(~f[1][1])ans++; 47 printf("%d",ans); 48 return 0; 49 } 50 } 51 signed main(){ 52 gengyf::main(); 53 return 0; 54 }