什么是树的重心？

一、树的重心

树的重心也叫树的质心。找到一个点，其所有的子树中最大的子树节点数最少，那么这个点就是这棵树的重心，删去重心后，生成的多棵树尽可能平衡。通俗点讲，就是在树中去掉一个点，删除这个点后，最大连通块(一定是树)的结点数最小。

举个例子：对于一颗n个节点的无根树，找到一个点，使得把树变成以该节点为根的有根树时，最大子树的节点数最少。换句话说，删除这个节点后最大连通块（一定是树）的节点数最少。

树的重心一些特性：树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。

把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。

● 一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。

● 一棵树最多有两个重心，且相邻。

二、性质

● 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。

● 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。

● 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。

● 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

三、求法

在 DFS 中计算每个子树的大小，记录“向下”的子树的最大大小，利用总点数 - 当前子树（这里的子树指有根树的子树）的大小得到“向上”的子树的大小，然后就可以依据定义找到重心了。

// 本代码默认节点编号从 1 开始，即 i ∈ [1,n]
int size[MAXN],  // 这个节点的“大小”（所有子树上节点数 + 该节点）
    weight[MAXN],  // 这个节点的“重量”
    centroid[2];   // 用于记录树的重心（存的是节点编号）

void GetCentroid(int cur, int fa) {  // cur 表示当前节点 (current)
  size[cur] = 1;
  weight[cur] = 0;
  for (int i = head[cur]; i != -1; i = e[i].nxt) {
    if (e[i].to != fa) {  // e[i].to 表示这条有向边所通向的节点。
      GetCentroid(e[i].to, cur);
      size[cur] += size[e[i].to];
      weight[cur] = max(weight[cur], size[e[i].to]);
    }
  }
  weight[cur] = max(weight[cur], n - size[cur]);
  if (weight[cur] <= n / 2) {  // 依照树的重心的定义统计
    centroid[centroid[0] != 0] = cur;
  }
}