似乎直接做不太好做……
当你不会做的时候就可以考虑根号算法了(或许是这样的
可以发现:对于链长\(>\sqrt{n}\)的所有值,最多只有\(\sqrt{n}\)种答案。
所以对于链长\(\leq \sqrt{n}\)暴力计算
对于链长\(> \sqrt{n}\),因为答案相等的链长一定是连续的(即如果链长为\(i\)的答案和链长为\(j\)的答案相等,那么对于\(\forall k \in [i,j]\),链长为\(k\)的答案一定和这两者相等),所以可以二分。设当前计算到了\(j\),先计算\(j\)的答案,然后二分出答案与\(j\)相等的区间的右端点\(k\),那么\([j,k]\)的答案都相等,输出\(k-j+1\)次答案,然后继续计算\(k+1\)。
这个算法的复杂度是\(O(n\sqrt{n} + n\sqrt{n}logn)\)的,还不够优秀。
可以发现分治的两种计算的复杂度是不平均的,优化一下
设小于等于\(S\)时暴力,大于\(S\)时二分,那么复杂度为\(O(nS + n \frac{n}{S} logn)\),不难得到当\(S= \sqrt{nlogn}\)时有最优复杂度\(O(n\sqrt{nlogn})\)
注意:计算某一种链长的答案不要使用递归,应先处理好拓扑序然后递推,这样可以大大加快程序运行速度。
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
bool f = 0;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = 1;
c = getchar();
}
if(c == EOF)
exit(0);
while(isdigit(c)){
a = (a << 3) + (a << 1) + (c ^ '0');
c = getchar();
}
return f ? -a : a;
}
const int MAXN = 1e5 + 10;
struct Edge{
int end , upEd;
}Ed[MAXN << 1];
int head[MAXN] , cur[MAXN] , top[MAXN] , fa[MAXN] , N , T , cntEd , ans , ts;
inline void addEd(int a , int b){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
void input(){
N = read();
T = sqrt(N * log2(N));
for(int i = 1 ; i < N ; ++i){
int a = read() , b = read();
addEd(a , b);
addEd(b , a);
}
}
void init(int x , int p){
fa[x] = p;
top[++ts] = x;
for(int i = head[x] ; i ; i = Ed[i].upEd)
if(Ed[i].end != p)
init(Ed[i].end , x);
}
void solve(int q){
ans = 0;
fill(cur + 1 , cur + N + 1 , 1);
for(int i = N ; i > 1 ; --i){
int x = top[i];
if(cur[fa[x]] != -1 && cur[x] != -1){
if(cur[fa[x]] + cur[x] >= q){
cur[fa[x]] = -1;
++ans;
}
else
cur[fa[x]] = max(cur[fa[x]] , cur[x] + 1);
}
}
}
void work(){
printf("%d\n" , N);
for(int i = 2 ; i <= T ; ++i){
solve(i);
printf("%d\n" , ans);
}
for(int j = T + 1 ; j <= N ; ){
solve(j);
int cur = ans , L = j , R = N;
while(L < R){
int mid = (L + R + 1) >> 1;
solve(mid);
if(ans == cur)
L = mid;
else
R = mid - 1;
}
while(j <= L){
++j;
printf("%d\n" , cur);
}
}
}
int main(){
input();
init(1 , 0);
work();
return 0;
}