树的重心求解

2020/10/06 09:08
阅读数 27

首先我们先要了解什么是树的重心在这里插入图片描述

树的重心定义为树的某个节点,当去掉该节点后,树的各个连通分量中,节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图,当去掉点1后,树将分成两个连通块: ( 2 , 4 , 5 ) (2,4,5) (2,4,5) ( 3 , 6 , 7 ) (3,6,7) (3,6,7),则最大的连通块包含节点个数为3。若去掉点2,则树将分成3个部分, ( 4 ) (4) (4) ( 5 ) (5) (5) ( 1 , 3 , 6 , 7 ) (1,3,6,7) (1,3,6,7)最大的连通块包含4个节点;第一种方法可以得到更小的最大联通分量。可以发现,其他方案不可能得到比3更小的值了。所以,点1是树的重心。

树的重心的一些性质:

  1. 删除重心后所得的所有子树,节点数不超过原树的1/2,一棵树最多有两个重心,且相邻;
  2. 树中所有节点到重心的距离之和最小,如果有两个重心,那么它们距离之和相等;
  3. 两个树通过一条边合并,新的重心在原树两个重心的路径上;
  4. 树删除或添加一个叶子节点,重心最多只移动一条边。

分析

任选一个节点为根,把无根树变成有根树,然后dp[i]表示以i为根的子树的节点个数。不难发现:

在这里插入图片描述

那么假设i是重心,在删除i之后 m a x ( d p [ j ] ) ( j ∈ S o n ( i ) ) max(dp[j]) (j∈Son(i)) max(dp[j])(jSon(i))还要与i上面的所有节点(可看成一棵子树)比,也就是n-dp[i]。右图中我们假设2号节点是重心,那么除了他们儿子节点为根的子树4和5以外,还有1367节点也可看成一棵子树,所以 f [ i ] = m a x ( m a x ( d p [ j ] ) , n − d p [ i ] ) f[i] = max(max(dp[j]),n-dp[i]) f[i]=max(max(dp[j]),ndp[i])

(f[i]就是以i为重心的最大子树节点数),那么答案就是 m i n ( f [ i ] ) ( i ∈ ( 1   n ) ) min(f[i])(i∈(1~n)) min(f[i])(i(1 n))

搜索时,还是递归到底层,回溯时进行累加,再利用重心的性质,所有子树的节点数不超过总节点数的 1 / 2 1/2 1/2,更新flag的值,就可以找到重心节点了。

代码

先以1为根节点,构造一棵树

#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 1e5 + 5;
vector<int> a[MAXN], v[MAXN];
int de[MAXN], fa[MAXN], dp[MAXN], f[MAXN];
bool vis[MAXN], flag[MAXN];
int n, m, ans;
void Find_Son(int);
void Find_Father(int);
void dfs(int, int);
void Init();
void Read();
void DP(int);
int main() {
   
   
	Read();
	Init();
	DP(1);
	for(int i = 1; i <= n; i++)
		if(flag[i])
			ans++;
	printf("%d\n", ans);
	for(int i = 1; i <= n; i++)
		if(flag[i])
			printf("%d\n", i);
	return 0;
}
void Find_Son(int now) {
   
   
	for(int i = 0; i < a[now].size(); i++) {
   
   
		if(!vis[a[now][i]]) {
   
   
			v[now].push_back(a[now][i]);
			vis[a[now][i]] = 1;
			Find_Son(a[now][i]);
		}
	}
}
void Find_Father(int now) {
   
   
	for(int i = 0; i < v[now].size(); i++) {
   
   
		fa[v[now][i]] = now;
		Find_Father(v[now][i]);
	}
}
void dfs(int now, int step) {
   
   
	de[now] = step;
	for(int i = 0; i < v[now].size(); i++)
		dfs(v[now][i], step + 1);
}
void Init() {
   
   
	vis[1] = 1;
	Find_Son(1); fa[1] = 1;
	Find_Father(1);
	dfs(1, 1);
}
void Read() {
   
   
	int A, B;
	scanf("%d", &n);
	for(int i = 1; i < n; i++) {
   
   
		scanf("%d %d", &A, &B);
		a[B].push_back(A);
		a[A].push_back(B);
	}
	for(int i = 1; i <= n; i++)
		flag[i] = 1;
}
void DP(int now) {
   
   
	dp[now] = 1;
	for(int i = 0; i < v[now].size(); i++) {
   
   
		DP(v[now][i]);
		dp[now] += dp[v[now][i]];
		if(dp[v[now][i]] > n / 2)
			flag[now] = 0;
	}
	if(n - dp[now] > n / 2)
		flag[now] = 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部