(mathcal{Description})
Link.
给定一棵含 (n) 个结点的树。称点集 (S) 到结点 (u) 的会合距离为 (sum_{vin S}operatorname{dist}(u,v))。对于 (|S|=1,2,dots,n)，求使得满足 (S) 一定且 (S) 到 (u) 的会合距离最小时，可能选取的 (u) 的个数的最大值。
(nle2 imes10^5)。
(mathcal{Solution})
可以发现，(u) 为 (S) 在树上的带权重心。不难得到以下结论：
- 当 (2 otmid|S|)，答案为 (1)；
- 若存在多个合法的 (u)，这些 (u) 构成一条树链，且树链上任意一条边满足：断开这条边，两个联通块中属于 (S) 的结点个数相等（这也印证了上个结论）。
考虑“枚举”树链更新答案。设一条树链两端结点构成的联通块大小为 (s_x,s_y)，则满足 (|S|le2min{s_x,s_y}) 的 (|S|) 的答案都能用这条链的长度更新。注意到需要维护全局联通块大小这一信息，尝试钦定全局根后在有向树上做点分治。每层分治更新答案时，可以钦定当前得到的联通块的小为某条树链较小的一端，正反分别做一遍，用树状数组就能维护。
复杂度 (mathcal O(nlog^2n))。
UPD：注意到点分治取重心的性质，跨过上层分治中心的路径一定不优，所以也可以直接统计以分治中心为根的子树大小。写的时候需要注意点分的实现，分治中心必须是严格的当前树上重心。Tiw 太强力！
(mathcal{Code})
/* Clearink */
#include <cstdio>
#include <vector>
#include <algorithm>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
inline int rint() {
int x = 0, f = 1, s = getchar();
for ( ; s < '0' || '9' < s; s = getchar() ) f = s == '-' ? -f : f;
for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' );
return x * f;
}
template<typename Tp>
inline void wint( Tp x ) {
if ( x < 0 ) putchar( '-' ), x = -x;
if ( 9 < x ) wint( x / 10 );
putchar( x % 10 ^ '0' );
}
inline void chkmax( int& a, const int b ) { a < b && ( a = b ); }
const int MAXN = 2e5, IINF = 0x3f3f3f3f;
int n, ecnt, head[MAXN + 5], ans[MAXN + 5];
int siz[MAXN + 5], par[MAXN + 5]; // for global root.
struct Edge { int to, nxt; } graph[MAXN * 2 + 5];
bool vis[MAXN + 5];
inline void link( const int u, const int v ) {
graph[++ecnt] = { v, head[u] }, head[u] = ecnt;
graph[++ecnt] = { u, head[v] }, head[v] = ecnt;
}
inline void findG( const int u, const int fa, int all, int& rt ) {
static int tsiz[MAXN + 5], wgt[MAXN + 5];
if ( !all ) all = tsiz[u];
tsiz[u] = 1, wgt[u] = 0;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( !vis[v = graph[i].to] && v != fa ) {
findG( v, u, all, rt ), tsiz[u] += tsiz[v];
chkmax( wgt[u], tsiz[v] );
}
}
chkmax( wgt[u], all - tsiz[u] );
if ( !rt || wgt[u] < wgt[rt] ) rt = u;
}
inline void init( const int u ) {
siz[u] = 1;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ( v = graph[i].to ) != par[u] ) {
par[v] = u, init( v );
siz[u] += siz[v];
}
}
}
struct BinaryIndexTree {
int val[MAXN + 5];
inline void upd( int x, const int v ) {
for ( x = n - x + 1; x <= n; x += x & -x ) chkmax( val[x], v );
}
inline int ask( int x ) {
int ret = -IINF;
for ( x = n - x + 1; x; x -= x & -x ) chkmax( ret, val[x] );
return ret;
}
inline void clear( int x ) {
for ( x = n - x + 1; x <= n; x += x & -x ) val[x] = -IINF;
}
} bit;
inline void update( const int u, const int fa, const int d, const int sr ) {
int su = u == par[fa] ? n - siz[u] : siz[u];
chkmax( ans[su << 1], bit.ask( su ) + d );
chkmax( ans[( su < sr ? su : sr ) << 1], d );
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( !vis[v = graph[i].to] && v != fa ) {
update( v, u, d + 1, sr );
}
}
}
inline void collect( const int u, const int fa, const int d ) {
int su = u == par[fa] ? n - siz[u] : siz[u];
bit.upd( su, d );
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( !vis[v = graph[i].to] && v != fa ) {
collect( v, u, d + 1 );
}
}
}
inline void clear( const int u, const int fa ) {
int su = u == par[fa] ? n - siz[u] : siz[u];
bit.clear( su );
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( !vis[v = graph[i].to] && v != fa ) {
clear( v, u );
}
}
}
inline void solve( const int u ) {
vis[u] = true;
static std::vector<int> son;
son.clear();
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( !vis[v = graph[i].to] ) {
son.push_back( v );
}
}
for ( int v: son ) {
update( v, u, 1, par[v] == u ? siz[u] - siz[v] : siz[u] );
collect( v, u, 1 );
}
for ( int v: son ) clear( v, u );
std::reverse( son.begin(), son.end() );
for ( int v: son ) {
update( v, u, 1, par[v] == u ? siz[u] - siz[v] : siz[u] );
collect( v, u, 1 );
}
for ( int v: son ) clear( v, u );
for ( int i = head[u], v, rt; i; i = graph[i].nxt ) {
if ( !vis[v = graph[i].to] ) {
findG( v, u, 0, rt = 0 );
solve( rt );
}
}
}
int main() {
n = rint();
rep ( i, 2, n ) link( rint(), rint() );
int rt = 0; findG( 1, 0, n, rt );
init( rt ); // let rt be global root.
rep ( i, 1, n ) bit.val[i] = -IINF;
solve( rt );
per ( i, n - 1, 1 ) chkmax( ans[i], ans[i + 1] );
rep ( i, 1, n ) wint( i & 1 ? 1 : ans[i] + 1 ), putchar( '
' );
return 0;
}