[CF768G] The Winds of Winter

Discription：

断开树的每一个点会形成一个森林，然后可以进行一次操作：将森林中的一棵树接到另一棵树上。使得森林中size最大的树size最小。依次输出对于每个结点的最小size值

Hint：

\(n<=1e5\)

Solution：

用multiset维护每个点的size域，每次贪心将最大的树的子树接到最小的树上，答案用二分答案求出

本题细节较多，需要处理各种情况

#include<bits/stdc++.h>

using namespace std;

typedef multiset<int >::iterator mit;

const int mxn=1e5+5;

struct ed {

	int to,nxt;

}t[mxn];

int n,rt,cnt;

int hd[mxn],sz[mxn],f[mxn],son[mxn],ans[mxn];

multiset<int >mp[mxn],oth,anc;

inline void add(int u,int v) {

	t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;

}

void dfs1(int u)

{

	sz[u]=1;

	for(int i=hd[u];i;i=t[i].nxt) {

		int v=t[i].to;

		dfs1(v); sz[u]+=sz[v];

		if(sz[v]>sz[son[u]]) son[u]=v;

	}

	if(u!=rt) oth.insert(sz[u]);

} //第一遍Dfs预处理出重儿子和初始size

inline int check(int opt,int val,int u,int mi,int mx)

{

	if(opt) {

		mit tp=mp[son[u]].lower_bound(mx-val);

		if(tp!=mp[son[u]].end()&&(*tp)+mi<=val) return 1;

	}

	else {

		mit tp=oth.lower_bound(mx-val);

		if(tp!=oth.end()&&(*tp)+mi<=val) return 1;

		tp=anc.lower_bound(mx-val+sz[u]);

		if(tp!=anc.end()&&(*tp)+mi-sz[u]<=val) return 1;

	}

	return 0;

} //分类讨论检验答案

void dfs2(int u)

{

	if(u!=rt) oth.erase(oth.lower_bound(sz[u])); //一开始删除，后面会加进来

	if(f[u]&&f[u]!=rt) anc.insert(sz[f[u]]);

	//因为祖先size是变化的，故将祖先单独拿出来维护

	int mx1=max(n-sz[u],sz[son[u]]); //子树size的最大值

	int mx2=min(n-sz[u],sz[son[u]]); //子树size的次大值

	int mi=n-sz[u]; //子树size的最小值

	if(!mi) mi=sz[son[u]];

	for(int i=hd[u];i;i=t[i].nxt) {

		int v=t[i].to;

		if(v==son[u]) continue ;

		dfs2(v);

		for(mit it=mp[v].begin();it!=mp[v].end();++it)

			oth.insert(*it);

		mi=min(mi,sz[v]),mx2=max(mx2,sz[v]);

	}

	if(son[u]) dfs2(son[u]),mi=min(mi,sz[son[u]]);

	for(int i=hd[u];i;i=t[i].nxt) {

		int v=t[i].to;

		if(v==son[u]) continue ;

		for(mit it=mp[v].begin();it!=mp[v].end();++it)

			oth.erase(oth.lower_bound(*it));

	}

	if(mx1!=mx2) {

		int l=mx2,r=mx1;

		int opt=(mx1==sz[son[u]]);

		while(l<=r) {

			int mid=(l+r)>>1;

			if(check(opt,mid,u,mi,mx1)) ans[u]=mid,r=mid-1;

			else l=mid+1;

		}

	} //当操作有意义时，二分答案

	if(!ans[u]) ans[u]=mx1;

	if(son[u]) swap(mp[u],mp[son[u]]);

	//每次直接O(1)继承重儿子的set，从而保证了时间复杂度

	for(int i=hd[u];i;i=t[i].nxt) {

		int v=t[i].to;

		if(v==son[u]) continue ;

		for(mit it=mp[v].begin();it!=mp[v].end();mp[v].erase(it++))

			mp[u].insert(*it);

	}

	if(f[u]&&f[u]!=rt) anc.erase(anc.lower_bound(sz[f[u]]));

	mp[u].insert(sz[u]);

}

void solve()

{

	dfs2(rt);

	for(int i=1;i<=n;++i) printf("%d\n",ans[i]);

}

int main()

{

	int u,v;

	scanf("%d",&n);

	for(int i=1;i<=n;++i) {

		scanf("%d %d",&u,&v);

		if(!u) rt=v;

		else add(u,v),f[v]=u;

	}

	dfs1(rt); solve();

	return 0;

}

巴特西

[CF768G] The Winds of Winter

Discription：

Hint：

Solution：

最新文章

热门文章