阅读程序-3解析
本题是求树的重心以及最大子节点树的节点数
一、树的重心的定义：
在一棵树中，如果我们选择某个结点为根，可以使得它的所有子树中最大的子树最小，那么这个结点就被称作这棵树的重心。
二、树重心的性质：
1．以重心为树根时，所有子树的大小不超过全树大小的一半。
2．如果树的所有边权都为1，那么树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。反过来，距离和最小的点一定是重心。
3．把两棵树通过一条边相连得到一棵新的树，则新的重心在较大的一棵树一侧的连接点与原重心之间的简单路径上。如果两棵树大小一样，则重心就是两个连接点。
另外一种说法：把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
4．在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
5．一颗树最多只有两个重心，且这两个重心一定是相邻的。此时树一定有偶数个节点，且可以被划分为两个大小相等的分支，每个分支各自包含一个重心。
6．一棵树的重心一定在根节点所在的重链上。
7．一棵树的重心一定是以该树根节点重儿子为根的子树的重心的祖先。
8．往树上增加或减少一个叶子，如果原节点数是奇数，那么重心可能增加一个，原重心仍是重心；如果原节点数是偶数，重心可能减少一个，另一个重心仍是重心。
三、找重心
遍历树，对每个点求 𝑓𝑢 表示最大子树。边遍历边求最小 𝑓𝑢。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | /**************************************************************** * Description: 2016_S_26 * Author: Alex Li * Date: 2023-09-07 14:43:47 * LastEditTime: 2023-09-07 15:32:03 ****************************************************************/ #include <iostream> #include <cstring> using namespace std; int map[100][100]; int sum[100], weight[100]; int visit[100]; int n; void dfs(int node)//参数是节点编号 { visit[node] = 1; //记录是否已标识 sum[node] = 1; //包括自己和子节点的节点数量，用来计算父节点的子树大小 int v, maxw = 0; for (v = 1; v <= n; v++)//邻接矩阵，遍历与node节点相连的边 { if (!map[node][v] || visit[v])//如相连且未访问过(防止访问父节点)，深搜 continue; dfs(v); sum[node] += sum[v];//统计包括自己的按深搜深度定义的node节点的子节点数量 if (sum[v] > maxw)//找到最大的子节点数(按深搜深度定义子节点) maxw = sum[v]; } if (n - sum[node] > maxw)//n-sum[node]是node节点的父节点子树，比较最大的子树节点数 maxw = n - sum[node]; weight[node] = maxw;//存储节点node最大子节点的节点数量(上下两个方向) } int main() { memset(map, 0, sizeof(map)); //初始化四个数组 memset(sum, 0, sizeof(sum)); memset(weight, 0, sizeof(weight)); memset(visit, 0, sizeof(visit)); cin >> n;//结点数 int i, x, y; for (i = 1; i < n; i++)//邻接矩阵，无向图存储 { cin >> x >> y; map[x][y] = 1; map[y][x] = 1; } dfs(1); int ans = n, ansN = 0; for (i = 1; i <= n; i++) //打到树的重心 if (weight[i] < ans)//最大子节点数量最小 { ans = weight[i];//重心的最大子节点数量 ansN = i; //重心节点编号 } cout << ansN << " " << ans << endl; return 0; } |