[数据结构与算法]2019徐州-Kill the tree-(树的重心+重心性质)

M

题意：
就是给你一个树，然后根节点为1，现在让你把每个子树的重心都输出。如果一个子树有两个重心，按升序输出。

思考：
我只会求一个树的重心，每个子树的重心怎么求呢，刚开始我还以为可以转化啥的，但是发现是不可行的，看了题解之后呢。其实重心有个性质，一个树的重心是他重儿子(节点个数最多的儿子)的重心和他的路径上面，但是到底是哪一个点呢？当从重儿子的重心不断往上走的过程中如果(cnt[now]-cnt[x])*2>cnt[now]证明now还有一个子树更大，所以还要往上走。走到最后如果(cnt[now]-cnt[x])*2==cnt[now]说名当前这个点是重心，但是这个点的父亲也是重心，画图一看就明白了，他俩的最大联通子块都是cnt[now]/2。所以此时now有了第二个重心记录下来就行了。
其实有一道题和这个几乎一样：Kay and Snowflake。这个题就是给你m次查询， 每次问你这个节点的子树的重心是什么。

代码：

int T,n,m,k;
int dep[N],acc[N],cnt[N],son[N];
int ans1[N],ans2[N];

vector<int > e[N];

void get(int now,int p)
{
	acc[now] = p;
	dep[now] = dep[p]+1;
	cnt[now] = 1;
	for(auto spot:e[now])
	{
		if(spot==p) continue;
		get(spot,now);
		cnt[now] += cnt[spot];
		if(cnt[son[now]]<cnt[spot]) son[now] = spot;
	}
	if(son[now]) //如果有重儿子
	{
		int x = ans1[son[now]]; //重儿子的重心
		while(x!=now&&(cnt[now]-cnt[x])*2>cnt[now]) x = acc[x]; //还不够，往上走
		ans1[now] = x; //重心
		if((cnt[now]-cnt[x])*2==cnt[now]) ans2[now] = acc[x]; //另一个重心
	}
	else ans1[now] = now; //如果没有重儿子意味着自己是根节点，那么重心就是他自己.
}

signed main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].pb(b);
		e[b].pb(a);
	}
	get(1,0);
	for(int i=1;i<=n;i++)
	{
		if(!ans2[i]) cout<<ans1[i]<<"\n";
		else cout<<min(ans1[i],ans2[i])<<" "<<max(ans1[i],ans2[i])<<"\n";
	}
	return 0;
}

总结：
多多思考，结合画图理解理解。