算法笔记：树的直径

定义：一棵树中任意两个节点之间最长的路径长度。

方法一：树形 DP（一次 DFS）

这种方法的核心思想是：对于每一个节点 $x$，经过它的最长路径是由其子树中延伸出来的最长链和次长链拼接而成的。

1. 核心逻辑

• dfs(x) 返回从节点 $x$ 出发向下的最长路径长度。
• 在递归过程中，利用子节点传回的长度 $t$，不断更新全局最大值 ans = max(ans, mx + t)，其中 mx 是之前遍历过的子树中的最长链。

2. 代码实现

#include <bits/stdc++.h>

using namespace std;

#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"

const int mod = 1e9 + 7;
const int N = 2e3 + 10, M = 2e3 + 10, INF = 0x3f3f3f3f;

int n, ans;           // n 为节点数，ans 用于存储全局最大直径
vector<int> g[N];    // 邻接表存储树

/**
 * DFS 函数：计算以 x 为根的子树中，从 x 出发向下的最长路径
 * @param x 当前节点
 * @param fa 当前节点的父节点，防止反向遍历
 * @return 返回从节点 x 向下延伸的最长路径长度（边数）
 */
int dfs(int x, int fa) {
    int mx = 0; // 记录在当前子树中，之前已遍历过的分支里的最长深度
    for (int y : g[x]) {
        if (y != fa) { // 不访问父节点
            int t = dfs(y, x); // 递归获取子节点 y 向下的最长距离

            // 核心逻辑：当前子树的最长距离 t 加上之前其他子树的最长距离 mx
            // 两者拼接即形成一条经过节点 x 的路径，尝试更新全局最大值
            ans = max(ans, mx + t);

            // 更新 mx，使其始终保持为从 x 向下走的最长单条路径
            mx = max(mx, t);
        }
    }
    // 返回以 x 为起点的最长路径深度（当前最大深度 + 1）
    return mx + 1;
}

void solve() {
    cin >> n;

    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    // 从 1 号节点开始 DFS 遍历
    dfs(1, 0);

    // 输出最终得到的树的直径
    cout << ans;
}

int main() {
    fast; 
    int T = 1;
    // cin >> T; 
    while (T--) {
        solve();
    }
    return 0;
}

3. 特点

• 优点：
  1. 只需一次 DFS，效率高。
  2. 可以处理带有负权边的情况。
• 缺点：逻辑相对抽象，不容易直接记录直径的具体路径。

方法二：两次 DFS（贪心法）

这是最直观的方法，基于一个性质：从任意点出发能找到的最远点，一定是直径的一个端点。

1. 核心步骤

1. 第一次 DFS：从任意节点 $u$ 出发，找到距离 $u$ 最远的节点 $p$。
2. 第二次 DFS：从节点 $p$ 出发，找到距离 $p$ 最远的节点 $q$。
3. 结论：$p$ 到 $q$ 的路径即为直径，距离即为直径长度。

2. 代码实现

#include <bits/stdc++.h>

using namespace std;

#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"

using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

const int mod = 1e9 + 7;
const int N = 2e3 + 10, M = 2e3 + 10, INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n;
vector<int> g[N];
int max_dist;  // 记录当前找到的最大距离
int far_point; // 记录当前找到的最远节点编号

/**
 * DFS 函数
 * @param x 当前节点
 * @param fa 父节点
 * @param dist 从起点到当前节点的累积距离
 */
void dfs(int x, int fa, int dist) {
    // 如果当前距离大于已知最大距离，更新最大距离和最远点
    if (dist > max_dist) {
        max_dist = dist;
        far_point = x;
    }

    for (int y : g[x]) {
        if (y != fa) {
            dfs(y, x, dist + 1);
        }
    }
}

void solve() {
    cin >> n;

    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    // 第一次 DFS：从 1 号点出发，寻找距离它最远的点 far_point
    max_dist = -1;
    dfs(1, 0, 0);

    // 第二次 DFS：从上一次找到的最远点 far_point 出发
    // 此时找到的最大距离 max_dist 即为树的直径
    max_dist = -1;
    dfs(far_point, 0, 0);

    cout << max_dist;
}

int main() {
    fast;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
} 

3. 特点

• 优点：
  1. 逻辑非常直观。
  2. 易于记录路径（通过在 DFS 时记录每个点的前驱节点即可）。
• 缺点：
  1. 需要两次 DFS。
  2. 无法处理负权边（若存在负权边，第一次 DFS 找到的不一定是直径端点）。

提示：

• 如果题目只要求长度且可能有负权 $\rightarrow$ 首选 树形 DP。
• 如果题目要求输出直径的具体路径 $\rightarrow$ 首选 两次 DFS。
• 在大多数数据结构题（边权全为 1）中，两者均可使用，但树形 DP 理论上常数更小。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com