似乎直接做不太好做……
当你不会做的时候就可以考虑根号算法了（或许是这样的
考虑如果只有一个询问如何计算答案。
显然是可以贪心的，思路与NOIP2018D1T3是相同的。每一个点向上传一条链，对于某一个点，如果从儿子传上来的所有链中最长的两条的长度之和\(\geq k\)就连上，否则就把其中最长的那一条传上去。
然后考虑所有询问。
可以发现：对于链长\(>\sqrt{n}\)的所有询问，最多只有\(\sqrt{n}\)种答案。
所以对于链长\(\leq \sqrt{n}\)的询问暴力计算
对于链长\(> \sqrt{n}\)的询问，因为答案随着链长增加单调不降，所以可以二分。设当前计算到了\(j\)，先算出\(j\)的答案，然后二分出答案与\(j\)相等的最大的\(k\)，那么对于\(\forall i \in [j,k]\)，链长为\(i\)的答案都相等，输出\(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//This code is written by Itstusing 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;}