题解 CF1039D 【You Are Given a Tree】

大菜鸡fks · 2018-10-07 20:51:24 · 题解

整体二分。 二分的答案用贪心验证。dp[u]表示u子树延伸上来的路径长度

#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){int x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}
inline void write(int x){if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0');}
inline void writeln(int x){write(x); puts("");}
const int N=1e5+5;
struct edge{
    int link,next;
}e[N<<1];
int n,tot,head[N];
inline void add_edge(int u,int v){
    e[++tot]=(edge){v,head[u]}; head[u]=tot;
}
inline void insert(int u,int v){
    add_edge(u,v); add_edge(v,u);
}
inline void init(){
    n=read();
    for (int i=1;i<n;i++){
        int u=read(),v=read();
        insert(u,v);
    }
}
int dp[N],ans[N],cnt;
void dfs(int u,int fa,int x){
    dp[u]=0; int mx1,mx2; mx1=mx2=0;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].link;
        if (v!=fa){
            dfs(v,u,x);
            if (dp[v]>mx1) mx2=mx1,mx1=dp[v];
                else mx2=max(mx2,dp[v]);
        }
    }
    if (mx1+mx2+1>=x) dp[u]=0,cnt++; else dp[u]=mx1+1;
}
void sol(int l,int r,int L,int R){
    if (l>r||L>R) return;
    if (L==R){
        for (int i=l;i<=r;i++) ans[i]=L;
        return;
    }
    int mid=(l+r)>>1; cnt=0; dfs(1,0,mid); ans[mid]=cnt;
    sol(l,mid-1,cnt,R); sol(mid+1,r,L,cnt);
}
inline void solve(){
    sol(1,n,0,n);
    for (int i=1;i<=n;i++) writeln(ans[i]);
}
int main(){
    init(); solve();
    return 0;
}