CF768G The Winds of Winter题解

我们考虑暴力咋做，每次得到一个森林之后，必定是从最大的树上摘一棵子树，挪到最小的树上，所以此时的答案为 \(max(siz_{mx}-x,siz_{mn}+x,siz_{次大值} )\)，于是发现 \(x=\frac{siz_{mx}-siz_{mn}}{2}\) 时答案最优，所以只需找到这个值的前驱后继即可

我们使用 \(\text{multiset}\) 实现，分别维护当前子树内，当前点到根路径，以及其他的点的子树大小
第二个是好维护的，对于第一个也可以启发式合并解决
对于第三种操作，我们可以现将全部点扔进去，到这个点的时候再删去子树内的点，这也可以树上启发式合并

以及注意一些乱七八糟的 \(conner\)

code

#include<bits/stdc++.h>
using namespace std;
#define N 100055
int n,k,rt;
int ans[N],h[N],sz[N],son[N];
multiset<int> oth[2],q[N];
struct AB{
	int a,b,n;
}d[N*2];
void cun(int x,int y){
	d[++k]={x,y,h[x]},h[x]=k;
}
void add(int x,int op){
	oth[op].insert(sz[x]);
}
void del(int x,int op){
	auto it=oth[op].lower_bound(sz[x]);
	oth[op].erase(it);
}
void dfs(int x,int fa){
	sz[x]=1,son[x]=0;
	for(int i=h[x];i;i=d[i].n){
		int y=d[i].b;
		if(y==fa) continue;
		dfs(y,x);sz[x]+=sz[y];
		if(sz[y]>sz[son[x]]) son[x]=y;
	}
	add(x,0);
}
void dfs1(int x,int fa,int op){
	if(!op) del(x,0);
	else add(x,0);
	for(int i=h[x];i;i=d[i].n){
		int y=d[i].b;
		if(y==fa) continue;
		dfs1(y,x,op);
	}
}
void solve(int x,int fa,int fl){
	del(x,0),add(x,1);
	for(int i=h[x];i;i=d[i].n){
		int y=d[i].b;
		if(y==fa||y==son[x]) continue;
		solve(y,x,0);
	}
	if(son[x]) solve(son[x],x,1);
	sz[n+1]=n-sz[x];
	int mx1=0,mx2=0,mn=n+2;
	if(x!=rt) mx1=n+1,mn=n+1;
	for(int i=h[x];i;i=d[i].n){
		int y=d[i].b;
		if(y==fa) continue;
		if(sz[y]>=sz[mx1]) mx2=mx1,mx1=y;
		else if(sz[y]>=sz[mx2]) mx2=y;
		if(sz[y]<sz[mn]) mn=y;
		if(y==son[x]) continue;
		dfs1(y,x,0);
	}
	del(x,1);
	if(sz[mx1]==sz[mn]) ans[x]=sz[mn];
	else if(mx1==n+1){
		for(int o=0;o<=1;o++){
			auto it=oth[o].upper_bound((sz[mx1]-sz[mn])/2+o*sz[x]);
			if(it!=oth[o].end()){
				int siz=*it-o*sz[x];
				ans[x]=min(ans[x],max(sz[mx1]-siz,max(sz[mx2],sz[mn]+siz)));
			}
			if(it!=oth[o].begin()){
				it--;
				int siz=*it-o*sz[x];
				ans[x]=min(ans[x],max(sz[mx1]-siz,max(sz[mx2],sz[mn]+siz)));
			}
		}
	}
	else{
		auto it=q[mx1].upper_bound((sz[mx1]-sz[mn])/2);
		if(it!=q[mx1].end()){
			int siz=*it;
			ans[x]=min(ans[x],max(sz[mx1]-siz,max(sz[mx2],sz[mn]+siz)));
		}
		if(it!=q[mx1].begin()){
			it--;
			int siz=*it;
			ans[x]=min(ans[x],max(sz[mx1]-siz,max(sz[mx2],sz[mn]+siz)));
		}
	}
	if(!fl) dfs1(x,fa,1);
	if(son[x]){
		swap(q[x],q[son[x]]);
		for(int i=h[x];i;i=d[i].n){
			int y=d[i].b;
			if(y==fa||y==son[x]) continue;
			for(auto num:q[y]) q[x].insert(num);
			q[y].clear();
		}
	}
	q[x].insert(sz[x]);
}
int main(){
	scanf("%d",&n);
	if(n==1){
		printf("0\n");
		return 0;
	}
	for(int i=1,x,y;i<=n;i++){
		scanf("%d%d",&x,&y);
		if(!x||!y) rt=x|y;
		else cun(x,y),cun(y,x);
	}
	memset(ans,9,sizeof(ans));
	dfs(rt,0);sz[n+2]=n+1;
	solve(rt,0,0);
	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}