题目大意：给你一棵树，让你对叶节点分组，保证每组中，任意两个叶节点之间的距离不大于K，求最小的组数
手动yy的贪心竟然对的
对于每个节点，维护一个$ma[i]$，表示在$i$节点的子树内 未被分组的叶节点到$i$节点的最长距离
那么，对于每个节点，把它的子节点按照$ma[i]$排序，那么如果这个点的子树不需要额外的分组，就要保证最大的$ma[v1]$和次大的$ma[v2]$之间的距离小于等于K
如果不满足，说明需要对子树内的节点进行额外分组
根据贪心的思想，选择ma最大的子节点$v1$，那么就从小往大一直找满足$ma[v1]+ma[vj]<=K$的点，当不满足条件时，说明刚才找过的小节点和那个较大的节点可以分成一组。接下来，要看次大$v2$的点能否满足更次大$v3$能否满足$ma[v2]+ma[v3]<=K$，找到说明可行，回溯。否则要继续刚才的过程，直到剩余子节点之间的最长距离<=K
因为每个节点只会以这种方式被遍历到一次，所以并不需要二分
1号节点可能是叶节点，所以不能直接把1当成根
另外，如果根节点的ma>1，说明根节点还剩下一些节点没被分组，把它们分到一组即可
1 #include <vector> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #define ll long long 6 #define N 1001000 7 #define uint unsigned int 8 #define inf 0x3f3f3f3f3f3f3fll 9 using namespace std; 10 //re 11 int gint() 12 { 13 int ret=0,fh=1;char c=getchar(); 14 while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();} 15 while(c>='0'&&c<='9'){ret=(ret<<3)+(ret<<1)+c-'0';c=getchar();} 16 return ret*fh; 17 } 18 19 int n,m,cte,num,S; 20 int head[N],fa[N],inc[N]; 21 struct Edge{int to,nxt;}edge[N*2]; 22 23 void ae(int u,int v){ 24 cte++;edge[cte].to=v,inc[v]++; 25 edge[cte].nxt=head[u],head[u]=cte; 26 } 27 28 vector<int>to[N]; 29 int ma[N]; 30 int cmp(int x,int y){return ma[x]<ma[y];} 31 int solve(int u){ 32 int ans=0,l,r; 33 for(int j=head[u];j;j=edge[j].nxt) 34 { 35 int v=edge[j].to; 36 if(v==fa[u]) continue; 37 to[u].push_back(v); 38 ans+=solve(v); 39 } 40 int tot=to[u].size(); 41 sort(to[u].begin(),to[u].end(),cmp); 42 if(!tot){ma[u]=1;return 0;} 43 if(tot==1){ma[u]=ma[to[u][tot-1]];} 44 else if(ma[to[u][tot-1]]+ma[to[u][tot-2]]<=m) 45 ma[u]=ma[to[u][tot-1]]; 46 else{ 47 l=0,r=tot-1; 48 while(r>0&&l<r&&ma[to[u][r]]+ma[to[u][r-1]]>m){ 49 for(;l<r&&ma[to[u][r]]+ma[to[u][l]]<=m;l++); 50 r--,ans++; 51 }ma[u]=ma[to[u][r]]; 52 }ma[u]+=(ma[u]>0?1:0);return ans; 53 } 54 55 56 int main() 57 { 58 scanf("%d%d",&n,&m); 59 int x,y; 60 for(int i=1;i<n;i++) 61 x=gint(),y=gint(),ae(x,y),ae(y,x); 62 for(int i=1;i<=n;i++) 63 if(inc[i]!=1) {S=i;break;} 64 dep[S]=1,dfs1(S,-1); 65 tp[S]=1,dfs2(S); 66 int ans=solve(S); 67 if(ma[S]-1>0) ans++; 68 printf("%d ",ans); 69 return 0; 70 }