LOJ 6042 跳蚤王国的宰相

题意

跳蚤王国爆发了一场动乱，国王在镇压动乱的同时，需要在跳蚤国地方钦定一个人来做宰相。

由于当时形势的复杂性，很多跳蚤都并不想去做一个傀儡宰相，带着宰相的帽子，最后还冒着被打倒并杀头的危险，然而有一只跳蚤却想得与众不同最时尚。

本来他打算去教书，他已经发表了自己在学术方面的见解，获得了很多跳蚤们的赞同，但是这时听说跳蚤国要钦定宰相，他毅然打断了想去教书的想法，他觉得只要为了国家利益，自己的生死都可以不管，哪里能因为工作能给自己带来灾祸或者福分就去避开或者接近这份工作呢？所以他决定站出来接了这份工作。

然而当时国王的钦定方式很奇怪，跳蚤王国可以看作一棵树，国王认为宰相必须更好的为跳蚤服务，所以他会选择一个到所有节点距离和最小的节点，并在这个节点中钦定，如果有多个节点满足距离和最小则任选一个。

然而跳蚤国的动乱实在是太厉害了，以至于树的形态可能也会发生改变，也就是说，树上可能会有若干条边消失，如果这个情况出现的话一定会有同样数目的边出现，以保证整个结构仍然是一棵树。

现在这个跳蚤想知道每个节点中的跳蚤如果要被钦定，至少需要多少条边消失（当然也会有同样数目的边出现）。作为这只跳蚤的一名真正的粉丝，你能帮他解决这个问题吗？

数据范围\(n\le 10^6\)

解题思路

为了行文方便,我们把一个一棵树称为过重的，当且仅当它的大小大于\(\frac{n}{2}\)

一个点是重心，当且仅当它的所有子树都不是过重的。

首先，对于这棵树的重心，它的答案一定为\(0\)。

对于非重心，它的过重的子树必然只有一个，且包含重心。

对于分裂出来的子树，我们把它接到我们期望它成为重心的点上一定不劣。

我们采取这样一种贪心的策略：先分裂重心的子树，从大到小。若某一时刻重心及重心的其他子树不过重，则可以把这一整颗树分裂出来。

接下来我们来证明这种策略的正确性。

首先，当重心以及重心的其他子树的大小不过重，而重心所在的子树依然过重，那么把重心分裂出来一定最优。

因为我们考虑到重心的任意一颗子树都不过重，那么只保留一颗子树一定是合法的。

我们把重心分裂出来其实就是保留重心的一颗子树的一部分，所以一定合法。

如果此时重心过重，那么重心所在的子树必定过重

所以必然要先把重心分裂到不过重

以上。

代码实现

我们把重心的所有子树按从大到小的顺序排序，然后二分。

就做完了。

#include<bits/stdc++.h>

#define now edge[i].v

#define go(x) for(int i=head[x];i;i=edge[i].nxt)

using namespace std;

const int sz=1e6+7;

const int inf=1e9;

int n;

int tot,rt;

int u,v,cnt;

int head[sz];

int ans[sz];

int mx[sz],siz[sz];

int s[sz],pos[sz],sum[sz];

struct Edge{

	int v,nxt;

}edge[sz<<1];

void make_edge(int u,int v){

	edge[++cnt]=(Edge){v,head[u]};head[u]=cnt;

	edge[++cnt]=(Edge){u,head[v]};head[v]=cnt;

}

bool cmp(int x,int y){

	return siz[x]>siz[y];

}

void getrt(int x,int fa){

	siz[x]=1;

	go(x) if(now!=fa){

		getrt(now,x);

		mx[x]=max(mx[x],siz[now]);

		siz[x]+=siz[now];

	}

	mx[x]=max(mx[x],n-siz[x]);

	if(mx[x]<tot) tot=mx[x],rt=x;

}

void dfs(int x,int fa){

	siz[x]=1;

	go(x) if(now!=fa){

		dfs(now,x);

		siz[x]+=siz[now];

	}

}

void Dfs(int x,int fa,int id){

	int w=n-siz[x];

	if(n-siz[id]<=n/2) ans[x]=(x!=id);

	else if(w-(sum[pos[id]-1])<=n/2){

		int l=0,r=pos[id]-1;

		while(l<r){

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

			if(w-sum[mid]<=n/2||n-siz[id]-sum[mid-1]<=n/2) r=mid;

			else l=mid+1;

		}

		ans[x]=l;

	}

	else{

		int l=pos[id]+1,r=tot;

		while(l<r){

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

			if(w-sum[mid]+siz[id]<=n/2||n-sum[mid-1]<=n/2) r=mid;

			else l=mid+1;

		}

		ans[x]=l-1;

	}

	go(x) if(now!=fa) Dfs(now,x,id);

}

void solve(){

	tot=0;

	go(rt) s[++tot]=now;

	sort(s+1,s+tot+1,cmp);

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

		pos[s[i]]=i;

		sum[i]=sum[i-1]+siz[s[i]];

	}

	go(rt) Dfs(now,rt,now);

}

int main(){

	scanf("%d",&n);

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

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

		make_edge(u,v);

	}

	tot=inf,rt=0;

	getrt(1,0);

	dfs(rt,0);

	solve();

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

}

巴特西

LOJ 6042 跳蚤王国的宰相