树的直径

给定一棵树，树中两点之间的距离定义为连接两点的路径边权之和，树的直径即是树中最远的两个节点之间的距离，这条路径被称为树的最长链。

树的直径可能不唯一（一棵树可以有多条最长链），但所有直径的长度一定相同。求树的直径有两种经典做法：树形 DP 与两次 DFS（BFS），时间复杂度均为 $O (n)$ 。

注意：本节中的树以 $n$ 个点 $n - 1$ 条边的无向图的形式给出，并存储在邻接表中。

两次 BFS/DFS 求树的直径

通过两次 BFS 或 DFS 也可以求出树的直径：从任一节点出发，通过 bfs 或 dfs 对树进行一次遍历，求出与出发点距离最远的节点，记为 p。从节点 p 出发，通过 bfs 或 dfs 再进行一次遍历，求出与 p 距离最远的节点 q。从 p 到 q 的路径就是树的一条直径（树的直径不唯一）。

定理：在一棵树上，从任一节点出发进行一次 bfs 或是 dfs，到达的距离其最远的节点 p 必为直径的一端。

既然 p 是直径的一端，那么与 p 距离最远的 q 自然就是直径的另一端。

证明思路（反证）：设 $s, t$ 为一条直径的两端， $z$ 为从任意点 $y$ 出发最远的点。若 $z$ 不是直径端点，分三种情况讨论 $y \to z$ 与 $s \to t$ 的位置关系： $y$ 在直径上、两条路径有公共部分、两条路径没有公共部分。三种情况都可以由 $δ (y, z) > δ (y, t)$ 推出 $δ (s, z) > δ (s, t)$ ，与 $δ (s, t)$ 是直径长度矛盾，故 $z$ 必为直径的一端。详细证明见 OI Wiki。

注意：上述证明建立在所有路径长度非负的基础上。如果树上存在负权边，则无法使用两次 BFS/DFS 的方式求解直径，此时只能使用树形 DP。

无权树的两次 DFS 实现：

cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, c, d[N];
vector<int> g[N];

void dfs(int u, int fa) {
	for (int v : g[u]) {
		if (v == fa) continue;
		d[v] = d[u] + 1;
		if (d[v] > d[c]) c = v;
		dfs(v, u);
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	dfs(1, 0); // 第一次 DFS 到达直径的一端 c
	d[c] = 0; dfs(c, 0); // 从 c 出发到达直径的另一端
	cout << d[c] << endl;

	return 0;
}

带边权并记录直径路径的实现：第二次 DFS 时记录每个点的前驱 pre，最后从终点 q 沿着 pre 一路走回起点 p，即可输出直径上的所有点。

cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], w[M], ne[M], idx;
LL dist[N];
int pre[N];
int n;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int x, int fa) {
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (y == fa) continue;
        dist[y] = dist[x] + w[i];
        pre[y] = x;
        dfs(y, x);
    }
}

int main() {
    cin >> n;
    memset(h, -1, sizeof h);

    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    int p = 1, q = 1;
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        if (dist[i] > dist[p]) p = i;

    dist[p] = 0, pre[p] = 0;
    dfs(p, 0);
    for (int i = 1; i <= n; i++)
        if (dist[i] > dist[q]) q = i;

    cout << dist[q] << endl;

    vector<int> path;
    for (int x = q; x; x = pre[x]) path.push_back(x);
    for (int x : path) cout << x << ' ';

    return 0;
}

边带权树的两次 BFS 实现：

cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 2 * N;
int h[N], e[M], w[M], ne[M], idx;
int n, d[N];

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

int bfs(int s) {
    memset(d, -1, sizeof d);
    queue<int> q;
    q.push(s); d[s] = 0;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (d[v] == -1) {
                d[v] = d[u] + w[i];
                q.push(v);
            }
        }
    }

    int p = s;
    for (int i = 1; i <= n; i++) {
        if (d[i] > d[p]) p = i;
    }

    return p;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b, c; cin >> a >> b >> c;

        add(a, b, c);
		add(b, a, c);
    }

    int p = bfs(1);
    int q = bfs(p);
    cout << d[q] << endl;

    return 0;
}

树形 DP 求树的直径

设 $d [x]$ 表示从 $x$ 出发、只往 $x$ 的子树方向走能到达的最远距离。枚举 $x$ 的儿子 $y$ （边权为 $w$ ）：

先用 $d [x] + d [y] + w$ 更新答案 $a n s$ ——这对应"经过 $x$ 的两条向下链拼成的最长路径"；
再用 $d [y] + w$ 更新 $d [x]$ —— $x$ 的最长向下链。

核心转移代码：

cpp

void dp(int x) {
    st[x] = true;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (st[y]) continue;
        dp(y);
        ans = max(ans, d[x] + d[y] + w[i]);
        d[x] = max(d[x], d[y] + w[i]);
    }
}

完整代码：

cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], w[M], ne[M], idx;
int d[N];
bool st[N];
int n, ans;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dp(int x) {
    st[x] = true;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (st[y]) continue;
        dp(y);
        ans = max(ans, d[x] + d[y] + w[i]);
        d[x] = max(d[x], d[y] + w[i]);
    }
}

int main() {
    cin >> n;
    memset(h, -1, sizeof h);

    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    dp(1);

    cout << ans << endl;

    return 0;
}

注：如果在建树时以无向图存储，则直接调用 dp(1) 即可得到答案 ans。如果建树时以有向图存储则求解 ans 需要这样做：for (int i = 1; i < n; i++) dp(i);

复杂度 $O (n)$ 。树形 DP 不依赖"最远点"的贪心性质，因此树上存在负权边时也可以用树形 DP 求解直径。

树的直径的相关性质

树可以有多条直径，它们的长度都等于树的直径长度。
若所有边权均为正，则所有直径的中点重合（反证：若两条直径 $s$ - $t$ 与 $s^{'}$ - $t^{'}$ 的中点 $x, x^{'}$ 不同，把两条直径各取一半经过 $x \to x^{'}$ 拼接，能得到比原直径更长的路径，矛盾）。
所有直径的公共部分是一条连续路径（可能缩成一个点），这是进阶例题 P3304 第二问的基础。

洛谷 B4016. 树的直径

给定一棵 $n$ 个结点的树（无边权），求树的直径，即树上最长的不重复经过一个点的路径长度。 $n \leq 10^{5}$ 。

直接用两次 DFS 即可（代码见上文"两次 BFS/DFS"小节）。

洛谷 P3304. [SDOI2013] 直径

给定一棵 $n$ 个结点的带权树，输出两行：第一行是直径长度，第二行是所有直径都经过的边数。 $n \leq 2 \times 10^{5}$ ， $0 \leq c \leq 10^{9}$ 。

做法：

两次 DFS 求出任意一条直径的两个端点 $S, T$ ，并记录直径上的点 $p a t h [1 \dots c n t]$ ；
对直径上的每个点，计算它"不经过直径边"能往下走的最远距离 $m x [x]$ ；
从左往右扫描直径，若 $m x [x]$ 等于 $x$ 到 $S$ 的距离，说明存在一条从 $x$ 的分支出发、与直径等长的路径，那么 $S$ 到 $x$ 之间的边不是必经边，更新左边界 $l$ ；
从右往左对称处理：若 $m x [x]$ 等于 $x$ 到 $T$ 的距离，则 $x$ 到 $T$ 之间的边不是必经边，更新右边界 $r$ ；
答案是 $r - l$ ，即两条边界之间的边数。

cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 200010, M = 2 * N;
int h[N], e[M], w[M], ne[M], idx;
LL dist[N], mx[N], ds[N], dt[N];
int pre[N], path[N];
bool on[N];
int n, cnt;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int x, int fa) {
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (y == fa) continue;
        dist[y] = dist[x] + w[i];
        pre[y] = x;
        dfs(y, x);
    }
}

LL deep(int x, int fa) {
    LL res = 0;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (y == fa || on[y]) continue;
        res = max(res, deep(y, x) + w[i]);
    }

    return res;
}

int main() {
    cin >> n;
    memset(h, -1, sizeof h);

    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    int S = 1, T = 1;
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        if (dist[i] > dist[S]) S = i;

    dist[S] = 0, pre[S] = 0;
    dfs(S, 0);
    for (int i = 1; i <= n; i++)
        if (dist[i] > dist[T]) T = i;

    cout << dist[T] << endl;  // 第一问：直径长度

    for (int x = T; x; x = pre[x]) path[++cnt] = x;  // 先得到 T -> S
    reverse(path + 1, path + 1 + cnt);                 // 翻转为 S -> T

    for (int i = 1; i <= cnt; i++) {
        on[path[i]] = true;
        ds[path[i]] = dist[path[i]];              // 到 S 的距离
        dt[path[i]] = dist[T] - dist[path[i]];    // 到 T 的距离
    }

    for (int i = 1; i <= cnt; i++)
        mx[path[i]] = deep(path[i], 0);           // 不经过直径边的最远距离

    int l = 1, r = cnt;
    for (int i = 1; i <= cnt; i++)
        if (mx[path[i]] == ds[path[i]]) l = i;
    for (int i = cnt; i >= 1; i--)
        if (mx[path[i]] == dt[path[i]]) r = i;

    cout << max(0, r - l) << endl;  // 第二问：所有直径的公共边数

    return 0;
}

习题

AcWing 1072. 树的最长路径（树形 DP 模板）
洛谷 P3629. [APIO2010] 巡逻（直径 + 边权取反）
洛谷 P1099. 树网的核（直径 + 双指针）
洛谷 P4408. [NOI2003] 逃学的小孩
洛谷 P2491. [SDOI2011] 消防（双倍经验！参见树网的核）

树的直径 ​

两次 BFS/DFS 求树的直径 ​

树形 DP 求树的直径 ​

树的直径的相关性质 ​

洛谷 B4016. 树的直径 ​

洛谷 P3304. [SDOI2013] 直径 ​