在刷初赛的过程中，发现了有一道读程序写结果题貌似是图论。题目如下：
#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++) { if (!map[node][v] || visit[v]) continue; dfs(v); sum[node] += sum[v]; if (sum[v] > maxw) maxw = sum[v]; } if (n - sum[node] > maxw) maxw = n - sum[node]; weight[node] = maxw; } 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; }
然后本人就一脸懵逼了：这道题究竟想要我们干什么？难不成要手动模拟吗？由于本蒟蒻很懒，所以首先放弃了手动模拟的做法。然后我就到网上搜了一下，发现了一个奇怪的东西：树的重心。
根据百度百科，树的重心的定义是：
找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心。
通俗来说，这句话的意思就是在一棵树上找到一个节点，删去这个节点后，所构成的树中节点个数最多的那棵树的节点要尽量少（也就是剩下的树的节点个数要尽可能平衡），那么我们把它称之为这棵树的重心。同时根据百度百科，我们显然也可以知道它的性质：
树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。
把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
一棵树最多有两个重心，且相邻。
那么如何来求树的重心呢？其实就是DFS找到每个节点的最大子树，然后标记一下子树的节点个数。最后输出的时候选最大子树节点个数最小的那个点即为树的重心。
所以回归到这道初赛题结果就显而易见了。
原文：https://www.cnblogs.com/decadent-slay/p/decadent_slay-algorithm.html