admin管理员组

文章数量:1026989

树的重心总结

树的重心

一、定义

树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值;

二、性质

1. 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
2. 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
3. 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
4. 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

三、求法

用搜索，搜索出以每个结点为根节点的子树上的节点个数，为子联通分量，则其的父连通分量为总个数减去子联通分量，再找到最小值即可；

四、代码

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAXN 105
using namespace std;
int n, dp[MAXN], dp1[MAXN], ans = 2147483647, ans1[MAXN], len, sum;
bool flag[MAXN];
vector < int > g[MAXN];
void dfs(int i) {dp[i] = 1;flag[i] = true;for (int t = 0; t < g[i].size(); t++) {int v = g[i][t];if (!flag[v]) {dfs(v);dp1[i] = max(dp1[i], dp[v]);dp[i] += dp[v];}}dp1[i] = max(dp1[i], n - dp[i]);return;
}
int main() {scanf("%d", &n);for (int i = 1; i < n; i++) {int x, y;scanf("%d %d", &x, &y);g[x].push_back(y);g[y].push_back(x);}dfs(1);for (int i = 1; i <= n; i++) {if (dp1[i] < ans) {ans = dp1[i];len = 1;ans1[len] = i;} else if (dp1[i] == ans) {ans1[++len] = i;}}printf("%d\n", len);for (int i = 1; i <= len; i++) {printf("%d\n", ans1[i]);}return 0;
}

树的重心总结

树的重心

一、定义

树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值;

二、性质

1. 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
2. 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
3. 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
4. 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

三、求法

用搜索，搜索出以每个结点为根节点的子树上的节点个数，为子联通分量，则其的父连通分量为总个数减去子联通分量，再找到最小值即可；

四、代码

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAXN 105
using namespace std;
int n, dp[MAXN], dp1[MAXN], ans = 2147483647, ans1[MAXN], len, sum;
bool flag[MAXN];
vector < int > g[MAXN];
void dfs(int i) {dp[i] = 1;flag[i] = true;for (int t = 0; t < g[i].size(); t++) {int v = g[i][t];if (!flag[v]) {dfs(v);dp1[i] = max(dp1[i], dp[v]);dp[i] += dp[v];}}dp1[i] = max(dp1[i], n - dp[i]);return;
}
int main() {scanf("%d", &n);for (int i = 1; i < n; i++) {int x, y;scanf("%d %d", &x, &y);g[x].push_back(y);g[y].push_back(x);}dfs(1);for (int i = 1; i <= n; i++) {if (dp1[i] < ans) {ans = dp1[i];len = 1;ans1[len] = i;} else if (dp1[i] == ans) {ans1[++len] = i;}}printf("%d\n", len);for (int i = 1; i <= len; i++) {printf("%d\n", ans1[i]);}return 0;
}

本文标签： 树的重心总结