Codeforces

分析

首先询问只有一个的时候很简单，差不多就是 NOIP2018D1T3 ，直接贪心即可。

考虑根号分治：

• 对于链长 $\leq B$ 的询问，直接暴力求。时间复杂度 $O(nB)$ 。
• 对于链长 $>B$ 的询问，可以发现答案只有至多 $\frac{n}{B}$ 种，直接二分出相同的段即可。时间复杂度 $O(n\frac{n}{B}\log n)$ 。

可以求出 $B=\sqrt{n\log n}$ 时复杂度最优。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,B;

vector<int> E[N];
inline void addEdge(int u,int v) { E[u].push_back(v); }

int fa[N],len[N],seq[N],top=0;
inline void dfs(int u,int f) {
    fa[u]=f,seq[++top]=u;
    for (re int v:E[u])
        if (v!=f) dfs(v,u);
}
inline int calc(int k) {
    for (re int i=1;i<=n;++i) len[i]=1;
    int ans=0;
    for (re int i=n;i>1;--i) {
        int u=seq[i],f=fa[u];
        if (len[f]!=-1&&len[u]!=-1) {
            if (len[f]+len[u]>=k) ++ans,len[f]=-1;
            else len[f]=max(len[f],len[u]+1);
        }
    }
    return ans;
}

int main() {
    n=read(),B=sqrt(n*log2(n));
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0);
    printf("%d\n",n);
    for (re int i=2;i<=B;++i) printf("%d\n",calc(i));
    for (re int i=B+1;i<=n;) {
        int now=calc(i),L=i,R=n;
        while (L<R) {
            int mid=(L+R+1)>>1;
            if (calc(mid)==now) L=mid;
            else R=mid-1;
        }
        for (;i<=L;++i) printf("%d\n",now);
    }
    return 0;
}