本课时有配套视频讲解，购买后即可观看（永久有效）

树的重心与直径

一、课上练习

编程练习

树的重心：L49972
树的直径：L49974

二、知识总结

✨ 核心思想

树的重心：删除该节点后，剩余各连通分量中最大的那个尽可能小的节点。重心是树的"平衡点"，在分治算法（点分治）中有重要应用。

树的直径：树上距离最远的两个节点之间的路径长度。直径是树的"最长路"，常用于求树上最远距离问题。

✨ 算法原理

树的重心

设 sz[u] 为以 u 为根的子树大小，n 为总节点数。删除 u 后，各连通分量的大小为：

各个子树的大小 sz[v]（v 是 u 的子节点）
除了 u 的子树之外的部分：n - sz[u]

删除 u 后的最大连通分量大小为：

maxPart(u) = max(max(sz[v]), n - sz[u])

重心就是使 maxPart(u) 最小的节点 u。

重心的重要性质：

重心最多有两个，且相邻
以重心为根时，所有子树大小不超过 n/2
树上所有点到重心的距离和最小

树的直径

方法一：两次 BFS/DFS

从任意节点 s 出发，找到距离 s 最远的节点 u
从 u 出发，找到距离 u 最远的节点 v
u 到 v 的距离就是直径

方法二：树形 DP

对于每个节点 u，计算经过 u 的最长路径
经过 u 的最长路径 = u 到子树中最远距离 + u 到子树中次远距离
所有节点中最大值即为直径

✨ 代码实现

1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int MAXN = 100005;
6vector<int> adj[MAXN];
7int sz[MAXN];     // 子树大小
8int maxp[MAXN];   // 删除该节点后最大连通分量大小
9int n;
10int centroid;     // 重心节点
11int minMaxPart;   // 最小的最大连通分量
12
13// DFS求子树大小，同时找重心
14void dfs(int u, int fa) {
15    sz[u] = 1;
16    maxp[u] = 0;
17
18    for (int v : adj[u]) {
19        if (v == fa) continue;
20        dfs(v, u);
21        sz[u] += sz[v];
22        // 记录u的最大子树
23        maxp[u] = max(maxp[u], sz[v]);
24    }
25
26    // 除了u的子树以外的部分
27    maxp[u] = max(maxp[u], n - sz[u]);
28
29    // 更新重心
30    if (maxp[u] < minMaxPart) {
31        minMaxPart = maxp[u];
32        centroid = u;
33    }
34}
35
36int main() {
37    cin >> n;
38    for (int i = 0; i < n - 1; i++) {
39        int u, v;
40        cin >> u >> v;
41        adj[u].push_back(v);
42        adj[v].push_back(u);
43    }
44
45    minMaxPart = n; // 初始化为最大值
46    dfs(1, 0);
47
48    cout << "重心：" << centroid << endl;
49    cout << "删除重心后最大连通分量大小：" << minMaxPart << endl;
50
51    return 0;
52}

1#include <iostream>
2#include <vector>
3#include <queue>
4#include <cstring>
5using namespace std;
6
7const int MAXN = 100005;
8vector<pair<int,int>> adj[MAXN]; // 邻接表，pair<终点, 边权>
9int dist[MAXN]; // 距离数组
10int n;
11
12// BFS求从起点s出发到所有点的距离，返回最远点
13int bfs(int s) {
14    memset(dist, -1, sizeof(dist));
15    queue<int> q;
16    q.push(s);
17    dist[s] = 0;
18    int farthest = s;
19
20    while (!q.empty()) {
21        int u = q.front();
22        q.pop();
23        for (auto& e : adj[u]) {
24            int v = e.first, w = e.second;
25            if (dist[v] == -1) {
26                dist[v] = dist[u] + w;
27                q.push(v);
28                if (dist[v] > dist[farthest]) {
29                    farthest = v;
30                }
31            }
32        }
33    }
34    return farthest;
35}
36
37int main() {
38    cin >> n;
39    for (int i = 0; i < n - 1; i++) {
40        int u, v, w;
41        cin >> u >> v >> w;
42        adj[u].push_back({v, w});
43        adj[v].push_back({u, w});
44    }
45
46    // 第一次BFS：从任意点出发，找最远点u
47    int u = bfs(1);
48    // 第二次BFS：从u出发，找最远点v
49    int v = bfs(u);
50
51    cout << "直径长度：" << dist[v] << endl;
52    cout << "直径端点：" << u << " 和 " << v << endl;
53
54    return 0;
55}

1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int MAXN = 100005;
6vector<pair<int,int>> adj[MAXN];
7int d1[MAXN]; // 子树中最远距离
8int d2[MAXN]; // 子树中次远距离
9int diameter; // 直径
10int n;
11
12void dfs(int u, int fa) {
13    d1[u] = d2[u] = 0;
14
15    for (auto& e : adj[u]) {
16        int v = e.first, w = e.second;
17        if (v == fa) continue;
18        dfs(v, u);
19
20        int dist = d1[v] + w; // 经过v到达的最远距离
21        if (dist > d1[u]) {
22            d2[u] = d1[u]; // 原来的最远变成次远
23            d1[u] = dist;
24        } else if (dist > d2[u]) {
25            d2[u] = dist;
26        }
27    }
28
29    // 经过u的最长路径 = 最远 + 次远
30    diameter = max(diameter, d1[u] + d2[u]);
31}
32
33int main() {
34    cin >> n;
35    for (int i = 0; i < n - 1; i++) {
36        int u, v, w;
37        cin >> u >> v >> w;
38        adj[u].push_back({v, w});
39        adj[v].push_back({u, w});
40    }
41
42    diameter = 0;
43    dfs(1, 0);
44    cout << "直径长度：" << diameter << endl;
45
46    return 0;
47}

✨ 执行示例

以下面的树为例（共 7 个节点，边权均为 1）：

1        1
2       / \
3      2   3
4     / \   \
5    4   5   6
6        |
7        7

求重心过程：

1DFS从1开始：
2  节点4: sz=1, maxp=max(0, 7-1)=6
3  节点7: sz=1, maxp=max(0, 7-1)=6
4  节点5: sz=2, maxp=max(1, 7-2)=5
5  节点2: sz=4, maxp=max(2, 7-4)=3
6  节点6: sz=1, maxp=max(0, 7-1)=6
7  节点3: sz=2, maxp=max(1, 7-2)=5
8  节点1: sz=7, maxp=max(4, 2, 0)=4
9
10各节点的maxp：4→6, 7→6, 5→5, 2→3, 6→6, 3→5, 1→4
11最小值为3，对应节点2 → 重心是节点2

两次 BFS 求直径：

1第一次BFS（从1出发）：
2  dist: 1→0, 2→1, 3→1, 4→2, 5→2, 6→2, 7→3
3  最远点：7（距离3）
4
5第二次BFS（从7出发）：
6  dist: 7→0, 5→1, 2→2, 4→3, 1→3, 3→4, 6→5
7  最远点：6（距离5）
8
9直径 = 5（路径：7→5→2→1→3→6）

✨ 解题步骤详解

求重心：

以任意节点为根进行 DFS
递归计算每个节点的子树大小 sz[u]
对每个节点计算 maxp[u] = max(最大子树, n - sz[u])
取 maxp 最小的节点即为重心

求直径（两次 BFS）：

从任意节点 BFS，找到最远节点 u
从 u 再 BFS，找到最远节点 v，dist[v] 即为直径
注意：此方法要求边权非负

求直径（树形 DP）：

以任意节点为根 DFS
维护每个节点到子树中的最远距离和次远距离
经过每个节点的最长路径 = 最远 + 次远
适用于边权为负的情况

✨ 常见错误

重心：忘记考虑 n - sz[u]：删除 u 后，除了子树外还有"上方"的部分
直径：两次 BFS 用于负权边：两次 BFS 方法不适用于有负边权的树
树形 DP 时更新次远距离的逻辑错误：应先判断是否超过最远，超过则更新两个值
忘记初始化：dist 数组、diameter 变量等需要正确初始化
无根树的 DFS 忘记避免走回父节点：需要传 fa 参数

✨ 算法评价

算法	时间复杂度	空间复杂度	适用条件
重心（DFS）	O(n)	O(n)	无限制
直径（两次 BFS）	O(n)	O(n)	边权非负
直径（树形 DP）	O(n)	O(n)	无限制

树的重心在点分治中是关键概念，选择重心作为分治中心可以保证递归深度为 O(log n)。树的直径在很多问题中用于求最远距离、最优选址等。