自动搬运

查看原文

来自洛谷，原作者为

	chenxinyang2006 退役了，生涯回忆有空的时候再写

搬运于2025-08-24 22:31:04，当前版本为作者最后更新于2024-01-23 09:44:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其他题解已经指出了事实上本题在 $j$ 为奇数时必定 puts 1；而在 $j$ 为偶数时等价于找一对点 $u,v$，以 $u$ 为根时 $v$ 子树大小 $\ge j$，以 $v$ 为根时 $u$ 子树大小 $\ge j$，输出最大的可能 $dis(u,v)$，这里 $dis(u,v)$ 代表 $u \to v$ 简单路径上点数。

考虑取重心为根，计算出每个点 $p$ 此时的子树大小 $siz_p$ 以及深度 $dep_p$。那么 $u,v$ 的位置关系有两种：

• $u,v$ 没有祖先后代关系，此时限制等价于 $\min(siz_u,siz_v) \ge j$。

• $u,v$ 有祖先后代关系，此时可以注意到把祖先的那个点调整到重心 $heavy$ 一定仍满足限制（以任意点为根，重心的子树大小都 $\ge \dfrac{n}{2} \ge j$；而这样调整后代点的子树大小不变）且 $dis(u,v)$ 只会增加。所以对于这类情况只需考虑祖先点为 $heavy$ 的 case。

进一步地，我们直接放弃掉 $u,v$ 应没有祖先后代关系的限制，认为只要 $\min(siz_u,siz_v) \ge j$ 就可以找到一组 $dis(u,v)$ 的解。这样做对答案没有影响，因为此时以 $u$ 为根 $v$ 的子树大小一定 $\ge \dfrac{n}{2}$ 而 $siz_v \le \dfrac{n}{2}$，相当于是加紧了限制。

于是把所有点按照 $siz$ 从大到小排序，维护前缀点集直径即可对每个 $j$ 算出 $\min(siz_u,siz_v) \ge j$ 的点对 $(u,v)$ 中 $dis(u,v)$ 最大的一对。

而祖先点是 $heavy$ 的 case 显然也容易 $O(n)$ 处理。

理论上，使用 $O(n)-O(1)$ LCA，本题可以做到线性。

在此给出使用 $O(n \log n)-O(1)$ LCA 的代码：

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n;
int result[100005];

int cnt;
int head[200005];
struct eg{
	int to,nxt;
}edge[400005];

void make(int u,int v){
	edge[++cnt].to = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}

int siz[200005],h[200005];
void dfs1(int u,int f){
	siz[u] = 1;
	h[u] = 0;
	for(int i = head[u];i;i = edge[i].nxt){
		int v = edge[i].to;
		if(v == f) continue;
		dfs1(v,u);
		siz[u] += siz[v];
		chkmax(h[u],siz[v]);
	}
}
int dfn[200005],dep[200005],fa[200005],ST[20][200005];
void dfs2(int u,int f){
	dfn[u] = ++cnt;
	ST[0][cnt] = u;
	dep[u] = dep[f] + 1;
	fa[u] = f;
	siz[u] = 1;
	for(int i = head[u];i;i = edge[i].nxt){
		int v = edge[i].to;
		if(v == f) continue;
		dfs2(v,u);
		siz[u] += siz[v];
	}
}
inline int cmp(int x,int y){
	if(dep[x] < dep[y]) return x;
	return y;
}

inline int qry(int l,int r){
	int x = __lg(r - l + 1);
	return cmp(ST[x][l],ST[x][r - (1 << x) + 1]);
}

inline int LCA(int u,int v){
	if(u == v) return u;
	u = dfn[u];v = dfn[v];
	if(u > v) swap(u,v);
	return fa[qry(u + 1,v)];
}

inline int getdis(int u,int v){
	return dep[u] + dep[v] - 2 * dep[LCA(u,v)];
}
int ord[200005];
bool cmp2(int x,int y){
	return siz[x] > siz[y];
}

int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n - 1){
		int u,v;
		scanf("%d%d",&u,&v);
		make(u,v);make(v,u);
	}
	dfs1(1,0);
	int rt = -1;
	rep(u,1,n) if(max(h[u],n - siz[u]) <= n / 2) rt = u;
	cnt = 0;
	dfs2(rt,0);
	rep(i,1,17){
		rep(j,1,n){
			if(j + (1 << i) - 1 > n) break;
			ST[i][j] = cmp(ST[i - 1][j],ST[i - 1][j + (1 << (i - 1))]); 
		}
	}
	rep(i,1,n) ord[i] = i;
	sort(ord + 1,ord + n + 1,cmp2);

	int pu = 0,pv = 0,pw = 0,t1,t2;
	rep(_i,1,n){
		int u = ord[_i];
		if(u == rt) continue;

		if(!pu){
			pu = pv = u;
			continue;
		}
		t1 = getdis(u,pu);t2 = getdis(u,pv);
		if(t1 >= max(t2,pw)){
			pw = t1;
			pv = u;
		}else if(t2 >= max(t1,pw)){
			pw = t2;
			pu = u;
		}
		chkmax(result[siz[u]],pw + 1);
	}
	rep(u,1,n) if(u != rt) chkmax(result[siz[u]],dep[u]);
	result[n / 2 + 1] = 1;
	per(i,n / 2,1) chkmax(result[i],result[i + 1]);
	rep(i,1,n){
		if(i % 2) printf("1\n");
		else printf("%d\n",result[i / 2]);
	}
	return 0;
}