AT_joisc2021_j

唯一的一篇题解用了点分治。太暴力了！这很蠢（指做法）。我们有一个优美的做法。

首先 $n$ 为奇数时，答案一定为 $1$。

证明：设答案点集为 $T$，则 $T$ 显然一定为一个连通块。考虑从 $T$ 中一个点 $x$ 移动到 $y$ 时，$S$ 中有些点对答案距离贡献增加，有些减少。只有这两者相等时答案不变。但是 $n$ 为奇数，不可能取等，所以 $|T|=1$。

类似地，我们发现当 $n$ 为偶数时，$T$ 中的点组成一条链。因为只有这样，从上述 $x$ 移动到 $y$ 时总贡献不变。

考虑拎出这条链的两个端点 $x,y$，那么要求就转化成，以这条链为根时，以 $x,y$ 为根的子树大小 $siz_x,siz_y\ge \frac{|S|}{2}$，并且这条链要尽可能长。

如果我们没有这个抽象的 $siz$ 的限制，那这个答案就是树的直径长度。但是有，怎么办呢。

发挥想象力，我们把每个点一开始看作独立的。每次发现有一个叶子 $x$ 不满足 $siz$ 的限制，我们就把他删掉。同时，将 $siz_{fa_x}\to siz_{fa_x}+siz_x$，也就是把 $x$ 并入 $fa_x$。动态维护。这样每次只会剩下可能被选作直径端点的点。使用拓扑排序实现。

于是变成了一个要求支持删点，查询直径长度的问题。删点难难难，但是这些修改和查询显然可以离线，进行一个时光的倒流，加点好好好。变成支持加点，查询直径长度。维护原来的直径两端点 $(x,y)$，加入 $u$，于是根据经典结论，直径一定是 $(x,y),(x,u),(y,u)$ 其一。于是每次查询树上两点距离即可。

做完了，时间复杂度 $O(n\log n)$。使用树剖求 LCA 跑的飞快，现在（24.7.15）是最优解并遥遥领先哈哈哈哈哈哈。

code：

int n,m,ans[N],deg[N];
bool vis[N];
int dep[N],fa[N],siz[N],son[N];
int cur,dfn[N],top[N];
priority_queue<pii> q;
vector<pii> g[N];
int tot,head[N];
struct node{
	int to,nxt;
}e[N<<1];
il void add(int u,int v){
	e[++tot]={v,head[u]},head[u]=tot;
}
void dfs1(int u,int f){
	siz[u]=1;
	fa[u]=f,dep[u]=dep[f]+1;
	go(i,u){
		int v=e[i].to;
		if(v==f){
			continue;
		}
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]){
			son[u]=v;
		}
	}
}
void dfs2(int u,int t){
	top[u]=t,dfn[u]=++cur;
	if(!son[u]){
		return;
	}
	dfs2(son[u],t);
	go(i,u){
		int v=e[i].to;
		if(v==fa[u]||v==son[u]){
			continue;
		}
		dfs2(v,v);
	}
}
il int getLca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]){
			swap(u,v);
		}
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
il int getDis(int u,int v){
	return dep[u]+dep[v]-2*dep[getLca(u,v)];
}
void Yorushika(){
	read(n);
	rep(i,1,n-1){
		int u,v;read(u,v);
		add(u,v),add(v,u);
		deg[u]++,deg[v]++;
	}
	dfs1(1,0),dfs2(1,1);
	rep(i,1,n){
		siz[i]=1;
		if(deg[i]<=1){
			q.emplace(-1,i);
		}
	}
	rep(j,1,n/2+1){
		while(q.size()&&-q.top().fi<j){
			int u=q.top().se;
			q.pop();
			vis[u]=1;
			go(i,u){
				int v=e[i].to;
				if(vis[v]){
					continue;
				}
				g[j].eb(u,v);
				siz[v]+=siz[u];
				if(--deg[v]==1){
					q.emplace(-siz[v],v);
				}
			}
		}
	}
	int x,y,len=1;
	x=y=q.top().se;
	drep(i,n/2+1,1){
		ans[i]=len;
		while(g[i].size()){
			auto [u,v]=g[i].back();
			g[i].pop_back();
			int A=getDis(x,y),B=getDis(x,u),C=getDis(y,u);
			if(B>A&&B>C){
				y=u;
			}else if(C>A){
				x=u;
			}
			len=max({A,B,C})+1;
		}
	}
	rep(i,1,n){
		if(i&1){
			puts("1");
		}else{
			printf("%d\n",ans[i/2]);
		}
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}

怎么就和出题人电波对上了。但是感觉可能只有 *2400 左右？