题意

给你\(n\)个点的树,其中一个简单路径的集合被称为\(k\)合法当且仅当树的每个节点最多属于一条路径,且每条路径包含\(k\)个节点。对于每个\(k(k \in [1,n])\),输出最多的\(k\)合法路径。

\(n\leq 10^5\)。

分析

• 先考虑 \(n^2\) 的做法，每次可以贪心地合并链，正确性显然。

• 考虑根号分治，\(k<\sqrt n\) 时 \(O(n)\) 暴力，否则因为取值是单调的可以二分，取值不超过 \(\frac{n}{\sqrt n}=\sqrt n\) 个。

• 总时间复杂度为 \(O(n\sqrt nlogn)\)。

• 因为这里两种操作的复杂度不均衡，所以可以把块的大小稍微调大。

根号分治的特点：\(x<\sqrt n\) 暴力个数和 \(x>\sqrt n\) 单个复杂度 \(\frac{n}{\sqrt n}=\sqrt n\)。

代码

#include<bits/stdc++.h>

using namespace std;

#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].lst,v=e[i].to)

#define rep(i,a,b) for(int i=a;i<=b;++i)

#define pb push_back

typedef long long LL;

inline int gi(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch))	{if(ch=='-') f=-1;ch=getchar();}

	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}

	return x*f;

}

template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}

template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}

const int N=1e5 + 7;

int n,t1,low,edc;

int ans[N],mx[N],head[N],fa[N];

vector<int>gg;

struct edge{

	int lst,to;

	edge(){}edge(int lst,int to):lst(lst),to(to){}

}e[N*2];

void Add(int a,int b){

	e[++edc]=edge(head[a],b),head[a]=edc;

	e[++edc]=edge(head[b],a),head[b]=edc;

}

void dfs(int u){

	go(u)if(v^fa[u]) {

		fa[v]=u,dfs(v);

	}

	gg.pb(u);

}

int solve(int k){

	int res=0;

	rep(i,1,n) mx[i]=1;

	for(auto u:gg){

		if(fa[u]&&mx[fa[u]]!=-1&&mx[u]!=-1){

			if(mx[u]+mx[fa[u]]>=k) ++res,mx[fa[u]]=-1;

			else Max(mx[fa[u]],mx[u]+1);

		}

	}

	return res;

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("data.in","r",stdin);

#endif

	n=gi();

	rep(i,1,n-1) Add(gi(),gi());

	int sz=min(400,n);

	dfs(1);

	ans[1]=n;

	rep(i,2,sz+1) ans[i]=solve(i);;

	for(int i=sz+1,j=sz+1;i<=n;i=j+1,j=i){

		int l=i,r=n,tmp=solve(i);

		while(l<r){

			int mid=l+r+1>>1;

			if(solve(mid)==tmp) l=mid;

			else r=mid-1;

		}

		j=l;

		rep(k,i,j) ans[k]=tmp;

	}

	rep(i,1,n) printf("%d\n",ans[i]);

	return 0;

}