EZOJ #389点分治好题

分析

一层一层把叶子去掉

看最多能去掉多少层即可

代码

#include<bits/stdc++.h>
using namespace std;
int vis[2000100],du[2000100],fa[2000100],n,m,ans;
int head[2000100],to[4000100],nxt[4000100],cnt;
int q[2000100],le,ri;
inline int ra(){
    int x=0;char s=getchar();
    while(!isdigit(s))s=getchar();
    while(isdigit(s))x=(x<<3)+(x<<1)+(s-'0'),s=getchar();
    return x;
}
inline void add(int x,int y){
    nxt[++cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
    nxt[++cnt]=head[y];
    head[y]=cnt;
    to[cnt]=x;
}
inline void dfs(int x,int f){
    fa[x]=f;
    for(int i=head[x];i;i=nxt[i])
      if(to[i]!=f)dfs(to[i],x);
}
int main(){
    int i,j,k;
    n=ra(),k=ra();
    k=n-k;
    for(i=1;i<n;++i){
      int x,y;
      x=ra(),y=ra();
      du[x]++,du[y]++;
      add(x,y);
    }
    dfs(1,0);
    le=1;
    for(i=1;i<=n;++i)if(du[i]==1)q[++ri]=i,vis[i]=1;
    while(ri>=le){
      int x=q[le];
      le++;
      k--;
      ans=max(ans,vis[x]);
      if(!k)break;
      for(i=head[x];i;i=nxt[i]){
          if(du[to[i]]<=1)continue;
          du[to[i]]--;
          vis[to[i]]=max(vis[to[i]],vis[x]+1);
          if(du[to[i]]==1)q[++ri]=to[i];
      }
    }
    printf("%d\n",ans);
    return 0;
}