admin管理员组

文章数量:1026989

树的重心。

文章目录

• 一、树重心的定义
• 二、性质
• • 2.dfs求重心

一、树重心的定义

对于树上的每一个点，以此节点为根时计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。说通俗点就是，删除此结点后，剩余连通块的结点数的最大值得到最小。

二、性质

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

2.dfs求重心

代码如下（示例）：

int dfs(int o, int fa) {int temp = 0;int sum = 0;for (int i = he[o]; i != -1; i = e[i].nxt) {int no = e[i].to;if (no == fa) continue;int num = dfs(no, o);temp = max(temp, num);sum += num;}temp = max(temp, n - sum - 1);nums[o] = temp;if(temp <= n / 2) ans.push_back(o);return sum + 1;
}

POJ 1655 Balancing Art
luoguP1364 医院设置
CodeForces 1406C Link Cut Centroids

树的重心。

文章目录

• 一、树重心的定义
• 二、性质
• • 2.dfs求重心

一、树重心的定义

对于树上的每一个点，以此节点为根时计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。说通俗点就是，删除此结点后，剩余连通块的结点数的最大值得到最小。

二、性质

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

2.dfs求重心

代码如下（示例）：

int dfs(int o, int fa) {int temp = 0;int sum = 0;for (int i = he[o]; i != -1; i = e[i].nxt) {int no = e[i].to;if (no == fa) continue;int num = dfs(no, o);temp = max(temp, num);sum += num;}temp = max(temp, n - sum - 1);nums[o] = temp;if(temp <= n / 2) ans.push_back(o);return sum + 1;
}

POJ 1655 Balancing Art
luoguP1364 医院设置
CodeForces 1406C Link Cut Centroids

本文标签： 树的重心