一、樹的重心

樹的重心也叫樹的質(zhì)心。找到一個點，其所有的子樹中最大的子樹節(jié)點數(shù)最少，那么這個點就是這棵樹的重心，刪去重心后，生成的多棵樹盡可能平衡。通俗點講，就是在樹中去掉一個點，刪除這個點后，最大連通塊(一定是樹)的結(jié)點數(shù)最小。

舉個例子：對于一顆n個節(jié)點的無根樹，找到一個點，使得把樹變成以該節(jié)點為根的有根樹時，最大子樹的節(jié)點數(shù)最少。換句話說，刪除這個節(jié)點后最大連通塊（一定是樹）的節(jié)點數(shù)最少。

樹的重心一些特性：樹中所有點到某個點的距離和中，到重心的距離和是最小的，如果有兩個重心，他們的距離和一樣。

把兩棵樹通過一條邊相連，新的樹的重心在原來兩棵樹重心的連線上。

● 一棵樹添加或者刪除一個節(jié)點，樹的重心最多只移動一條邊的位置。

● 一棵樹最多有兩個重心，且相鄰。

二、性質(zhì)

● 以樹的重心為根時，所有子樹的大小都不超過整棵樹大小的一半。

● 樹中所有點到某個點的距離和中，到重心的距離和是最小的；如果有兩個重心，那么到它們的距離和一樣。

● 把兩棵樹通過一條邊相連得到一棵新的樹，那么新的樹的重心在連接原來兩棵樹的重心的路徑上。

● 在一棵樹上添加或刪除一個葉子，那么它的重心最多只移動一條邊的距離。

三、求法

在 DFS 中計算每個子樹的大小，記錄“向下”的子樹的最大大小，利用總點數(shù) - 當(dāng)前子樹（這里的子樹指有根樹的子樹）的大小得到“向上”的子樹的大小，然后就可以依據(jù)定義找到重心了。

// 本代碼默認節(jié)點編號從 1 開始，即 i ∈ [1,n]
int size[MAXN],  // 這個節(jié)點的“大小”（所有子樹上節(jié)點數(shù) + 該節(jié)點）
    weight[MAXN],  // 這個節(jié)點的“重量”
    centroid[2];   // 用于記錄樹的重心（存的是節(jié)點編號）

void GetCentroid(int cur, int fa) {  // cur 表示當(dāng)前節(jié)點 (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 表示這條有向邊所通向的節(jié)點。
      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) {  // 依照樹的重心的定義統(tǒng)計
    centroid[centroid[0] != 0] = cur;
  }
}