树的重心(质心) Centroid of a Tree

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

算法

先任选一个结点作为根，把无根树变成有根树，然后设 $d(i)$ 表示以 $i$ 为根的子树的结点个数。不难发现 $d(i)=\sum_{j\in s(i)} d(j)+1$ 。

所以算法就是：任选一个节点作为根，进行DFS，同时计算 $d(i)$ 。这时所有 $i$ 的子树中，最大的子树有max{ $d(j)$ }个结点， $i$ 的“上方子树”中有 $n-d(i)$ 个结点。

DFS可以做到当 $d(i)$ 大于等于 $n/2$ 时停止，因为不难看到，当 $i$ 是重心时，所有子树的大小都不会超过整棵树的一半大小。

代码：

// 这份代码默认节点编号从 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;
  }
}

习题
POJ1655		Balancing Act
P1364		医院设置		普及/提高-