跳转至

# 树的中心

## 定义

在树中，如果节点 𝑥 x 作为根节点时，从 𝑥 x 出发的最长链最短，那么称 𝑥 x 为这棵树的中心．

## 性质

- 树的中心不一定唯一，但最多有 2 2 个，且这两个中心是相邻的．
- 树的中心一定位于树的直径上．
- 树上所有点到其最远点的路径一定交会于树的中心．
- 当树的中心为根节点时，其到达直径端点的两条链分别为最长链和次长链．
- 当通过在两棵树间连一条边以合并为一棵树时，连接两棵树的中心可以使新树的直径最小．
- 树的中心到其他任意节点的距离不超过树直径的一半．

## 求法

寻找一个点 𝑥 x，使其作为根节点时，最长链的长度最短．

### 具体步骤

1. 维护 𝑙 𝑒 𝑛 1 𝑥 l e n 1 x，表示节点 𝑥 x 子树内的最长链．
2. 维护 𝑙 𝑒 𝑛 2 𝑥 l e n 2 x，表示不与 𝑙 𝑒 𝑛 1 𝑥 l e n 1 x 重叠的最长链．
3. 维护 𝑢 𝑝 𝑥 u p x，表示节点 𝑥 x 子树外的最长链，该链必定经过 𝑥 x 的父节点．
4. 找到点 𝑥 x 使得 m a x(𝑙 𝑒 𝑛 1 𝑥,𝑢 𝑝 𝑥)max(l e n 1 x,u p x) 最小，那么 𝑥 x 即为树的中心．

参考代码

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    // 这份代码默认节点编号从 1 开始，即 i ∈ [1,n]，使用vector存图
    int d1[N], d2[N], up[N], x, y, mini = 1e9;  // d1,d2对应上文中的len1,len2

    struct node {
      int to, val;  // to为边指向的节点，val为边权
    };

    vector<node> nbr[N];

    void dfsd(int cur, int fa) {  // 求取len1和len2
      for (node nxtn : nbr[cur]) {
        int nxt = nxtn.to, w = nxtn.val;  // nxt为这条边通向的节点，val为边权
        if (nxt == fa) {
          continue;
        }
        dfsd(nxt, cur);
        if (d1[nxt] + w > d1[cur]) {  // 可以更新最长链
          d2[cur] = d1[cur];
          d1[cur] = d1[nxt] + w;
        } else if (d1[nxt] + w > d2[cur]) {  // 不能更新最长链，但可更新次长链
          d2[cur] = d1[nxt] + w;
        }
      }
    }

    void dfsu(int cur, int fa) {
      for (node nxtn : nbr[cur]) {
        int nxt = nxtn.to, w = nxtn.val;
        if (nxt == fa) {
          continue;
        }
        up[nxt] = up[cur] + w;
        if (d1[nxt] + w != d1[cur]) {  // 如果自己子树里的最长链不在nxt子树里
          up[nxt] = max(up[nxt], d1[cur] + w);
        } else {  // 自己子树里的最长链在nxt子树里，只能使用次长链
          up[nxt] = max(up[nxt], d2[cur] + w);
        }
        dfsu(nxt, cur);
      }
    }

    void GetTreeCenter() {  // 统计树的中心，记为x和y（若存在）
      dfsd(1, 0);
      dfsu(1, 0);
      for (int i = 1; i <= n; i++) {
        if (max(d1[i], up[i]) < mini) {  // 找到了当前max(len1[x],up[x])最小点
          mini = max(d1[i], up[i]);
          x = i;
          y = 0;
        } else if (max(d1[i], up[i]) == mini) {  // 另一个中心
          y = i;
        }
      }
    }

### 示例

假设我们有一棵树，如下所示：

    1
    2
    3
    4
    5
               A
              / \
             B   C
            / \   \
           D   E   F

- 树的直径为 𝐷 →𝐵 →𝐴 →𝐶 →𝐹 D→B→A→C→F．直径长度为 4 4．
- 树的中心为节点 𝐴 A，因为从 𝐴 A 出发的最长链（到 𝐷 D 或 𝐹 F）均为 2 2．
- 如果将 𝐵 B 或 𝐶 C 作为树的根，则从这些节点出发的最长链将增加，因此它们不是树的中心．

### 时间复杂度

上述算法的时间复杂度为 𝑂(𝑛)O(n)，其中 𝑛 n 是树中节点的数量．

## 参考

- TutorialsPoint: Centers of a Tree
- ProofWiki: Definition of Center of Tree
- Wikipedia: Tree (graph theory)

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：littleparrot12345, Tiphereth-A
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用