文章

25

粉丝

0

获赞

0

访问

244721

头像
树的重心
经验总结
发布于2020年4月21日 23:12
阅读数 9489

树的重心:对于一颗n个节点的无根树,找到一个点,使得把树变成以该节点为根的有根树时,最大子树的节点数最小,也就是说删除这个点后最大联通块的节点数最小。

如果要以i为重心的话,那么其最大子树的节点数就是max(max(dp[j]), n - dp[i]),其中j为i的孩子节点。

树的重心的性质:

    性质 1 :树中所有点到某个点的距离和中,到重心的距离和是最小的,如果有两个重心,他们的距离和一样。

    性质 2 :把两棵树通过某一点相连得到一颗新的树,新的树的重心必然在连接原来两棵树重心的路径上。

    性质 3 :一棵树添加或者删除一个节点,树的重心最多只移动一条边的位置。

dfs:树的重心模板:

int mins, id;
void dfs(int u, int father){
	dp[u] = 1;
	int maxs = 0;
	for (int i = h[u]; i; i = next_pos[i]){
		int j = e[i];
		if (j == father){
			continue;
		}
		dfs(j, u);
		dp[u] += dp[j];
		maxs = max(maxs, dp[v]);
	}
	maxs = max(maxs, n - dp[u]);
	if (maxs < mins){
		mins = maxs;
		id = u;
	}
}

------------------------------------------------------------

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int t, n;
int h[N], dp[N];//dp[N]表示以i为根节点的树的节点个数
int e[N], next_pos[N], idx;
void add(int a, int b){
	e[++idx] = b;
	next_pos[idx] = h[a];
	h[a] = idx;
}
int mins, id;
void dfs(int u, int father){
	dp[u] = 1;
	int maxs = 0;//最大节点的子树
	for (int i = h[u]; i; i = next_pos[i]){
		int j = e[i];
		if (j == father){ continue; }
		dfs(j, u);
		dp[u] += dp[j];
		maxs = max(maxs, dp[j]);
	}
	maxs = max(maxs, n - dp[u]);
	if (maxs < mins){
		mins = maxs;
		id = u;
	}
}
int main(){
	cin >> t;
	while (t--){
		cin >> n;
		int u, v;
		for (int i = 1; i <= n - 1; i++){
			cin >> u >> v;
			add(u, v); add(v, u);
		}
		mins = 0x3f3f3f3f;
		dfs(1, 0);
		cout << id << " " << mins << endl;
	}
	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发