题解 CF1632E2 【Distance Tree (hard version)】
meyi
·
·
题解
首先，连出的边的一个端点必定为 1，因为以其他点为端点不会使答案变的更优。
假如我们已经得到 f(x)，需要反推方案，那么只用考虑深度 >f(x) 的节点，因为对深度 \le f(x) 的节点连边没有意义。
令 dis_{ans} 表示深度 >ans 的节点两两之间的最大距离，则有 ans\ge\lceil \frac{dis_{ans}}{2}\rceil+x。
考虑这个不等式的意义，它其实是将深度 >ans 的节点拉出来建了个虚树，然后连了 (1,直径中点) 这条边，这样做显然最优，那么此时的最大深度显然是 \lceil\frac{dis_{ans}}{2}\rceil+x，由于 ans 合法，所以有 ans\ge\lceil\frac{dis_{ans}}{2}\rceil+x。
由于 ans 增大会使深度 >ans 的节点数量减少，所以 dis_{ans} 是单调减的，这就可以使用二分 O(n\log n) 计算了。
进一步考虑，x 增大只会使 ans 增大，所以直接 O(n) 计算就完事了。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxn=3e5+10;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));}
int dis[maxn];
vector<int>e[maxn];
int dfs(int p,int f,int d){
ri a=0,b=0;
for(ri i:e[p])
if(i!=f){
ri c=dfs(i,p,d+1)+1;
if(c>a)b=a,a=c;
else ckmax(b,c);
}
if(b+d)ckmax(dis[b+d-1],(a+b+1)>>1);
return a;
}
int n,t_case;
int main(){
scanf("%d",&t_case);
while(t_case--){
scanf("%d",&n);
for(ri i=1;i<=n;++i)dis[i]=0,vector<int>().swap(e[i]);
for(ri i=1,x,y;i<n;++i){
scanf("%d%d",&x,&y);
e[x].push_back(y),e[y].push_back(x);
}
ri lim=dfs(1,0,0);
for(ri i=n-2;~i;--i)ckmax(dis[i],dis[i+1]);
ri ans=1;
for(ri i=1;i<=n;++i){
while(dis[ans]+i>ans)++ans;
printf("%d%c",min(ans,lim)," \n"[i==n]);
}
}
return 0;
}
```