树的重心与求法

__ryp__ · 2023-12-17 15:43:16 · 个人记录

重心的定义与性质

一棵树的重心是这样的点：将它删除后，它的所有子树的节点数量的最大值，在所有节点中最小。

重心最重要的性质是：一棵树上所有点到重心的距离和是最短的。

重心的求法

我们可以用一个简单的 DFS 算法来求重心。

对每一个节点，我们在 DFS 中统计它的子树节点数量，并且取得其最大值 t。我们知道，将这个节点删除后，整个图中除了它的子树，还有它的父亲所在的子树。它父亲所在的子树的节点数量，很明显是树的总节点数量减去这个节点的子树节点数量，也就是 n - t。

设 p = \max (n - t, t)，则我们只需要找到使 p 最小的节点即可。

int
centroid (int p, int father)
{
  int weight = 0;
  sizep[p] = 1;

  for (auto t : e[p])
      if (t != father) weight = max (weight, sizep[p] += centroid (t, p););

  weight = max (weight, n - sizep[p]);
  if (weight < mw) mw = weight, center = p;
  return sizep[p];
}

则 center 就是重心。