别再死记模板！用两种方法（DFS和树形DP）搞定树的直径，C++代码逐行解析

深入解析树的直径：从DFS到树形DP的C++实战指南

树结构在算法竞赛和实际工程中无处不在，而树的直径作为衡量树规模的重要指标，其求解方法一直是面试和竞赛中的高频考点。很多学习者虽然能背诵模板代码，却对背后的原理一知半解。本文将彻底拆解两种主流解法——两次DFS法和树形DP法，通过可视化分析、复杂度对比和典型用例，带你真正掌握这一核心算法。

1. 树的直径基础与两次DFS法

树的直径定义为树中任意两节点间最长路径的长度。想象一下，如果这棵树是城市间的道路网，直径就是相隔最远的两个城市之间的距离。这个看似简单的概念，在实际应用中却有着丰富的变体和求解技巧。

1.1 两次DFS法的核心原理

两次DFS法基于一个关键定理：从任意节点出发进行DFS，到达的最远节点必然是直径的一个端点。这个结论的直观理解是：直径作为树中最长的路径，其端点必然是彼此最远的两个节点。

void dfs(int u, int fa, int depth, int& maxDepth, int& farthestNode) { if (depth > maxDepth) { maxDepth = depth; farthestNode = u; } for (int v : adj[u]) { if (v != fa) { dfs(v, u, depth + 1, maxDepth, farthestNode); } } }

表：DFS关键参数说明

1.2 算法实现与复杂度分析

完整的两步DFS实现如下：

pair<int, int> findDiameterDFS(vector<vector<int>>& tree) { int n = tree.size(); int end1 = 0, maxDepth = 0; // 第一次DFS：从任意节点（这里选0）找到最远节点end1 function<void(int, int, int)> dfs = [&](int u, int fa, int depth) { if (depth > maxDepth) { maxDepth = depth; end1 = u; } for (int v : tree[u]) { if (v != fa) dfs(v, u, depth + 1); } }; dfs(0, -1, 0); // 第二次DFS：从end1出发找到最远节点end2 int end2 = end1, diameter = 0; maxDepth = 0; dfs(end1, -1, 0); diameter = maxDepth; end2 = end1; // 注意这里end1已被更新为最远节点 return {diameter, end2}; }

时间复杂度：O(n)，每个节点被访问两次
空间复杂度：O(n)，递归栈空间和邻接表存储

注意：该方法仅适用于边权均为正的情况。若存在负权边，最远节点可能不在直径端点上。

2. 树形DP：处理负权边的通用解法

当树中存在负权边时，两次DFS法失效。这时需要更强大的工具——树形动态规划。这种方法不仅适用于所有边权情况，还能在求解过程中获得更多子树信息。

2.1 树形DP的核心思想

定义两个状态数组：

• d1[u]：以u为根的子树中，u到叶子节点的最长路径
• d2[u]：以u为根的子树中，u到叶子节点的次长路径（与最长路径无公共边）

树的直径就是所有节点中d1[u] + d2[u]的最大值。这种方法的精妙之处在于，它通过后序遍历自底向上地计算每个子树的贡献。

int diameter = 0; void dfsDP(int u, int fa) { d1[u] = d2[u] = 0; for (auto [v, w] : adj[u]) { if (v == fa) continue; dfsDP(v, u); int t = d1[v] + w; if (t > d1[u]) { d2[u] = d1[u]; d1[u] = t; } else if (t > d2[u]) { d2[u] = t; } } diameter = max(diameter, d1[u] + d2[u]); }

2.2 带权树的实现变体

对于带权树，我们需要在状态转移时考虑边权。以下是支持负权边的完整实现：

struct Edge { int to, weight; }; vector<vector<Edge>> adj; vector<int> d1, d2; int diameter; void computeDiameter() { int n = adj.size(); d1.assign(n, 0); d2.assign(n, 0); diameter = 0; function<void(int, int)> dfs = [&](int u, int fa) { for (auto [v, w] : adj[u]) { if (v == fa) continue; dfs(v, u); int t = d1[v] + w; if (t > d1[u]) { d2[u] = d1[u]; d1[u] = t; } else if (t > d2[u]) { d2[u] = t; } } diameter = max(diameter, d1[u] + d2[u]); }; dfs(0, -1); }

表：树形DP状态转移分析

3. 两种方法的深度对比与选择策略

3.1 性能与适用场景对比

表：DFS与DP方法对比

3.2 典型应用场景分析

1. 网络延迟分析：在计算机网络中，树的直径可以反映最坏情况下的通信延迟。如果边权表示延迟时间，必须使用树形DP法。

2. 社交网络影响传播：在社交网络树形结构中，直径两端的人物通常是信息传播的关键节点。此时使用两次DFS法更高效。

3. 资源分配优化：如医院选址问题，需要同时考虑树的重心和直径特性，这时树形DP法能提供更多子树信息。

// 医院选址问题中的综合应用示例 void findOptimalLocation(vector<vector<Edge>>& tree, vector<int>& population) { vector<int> totalDist(tree.size(), 0); vector<int> subtreeSize(tree.size(), 0); int minTotalDist = INT_MAX; int bestLocation = 0; function<void(int, int)> dfs = [&](int u, int fa) { subtreeSize[u] = population[u]; for (auto [v, w] : tree[u]) { if (v == fa) continue; dfs(v, u); subtreeSize[u] += subtreeSize[v]; totalDist[u] += totalDist[v] + subtreeSize[v] * w; } }; function<void(int, int, int)> reroot = [&](int u, int fa, int n) { if (totalDist[u] < minTotalDist) { minTotalDist = totalDist[u]; bestLocation = u; } for (auto [v, w] : tree[u]) { if (v == fa) continue; totalDist[v] = totalDist[u] + (n - 2 * subtreeSize[v]) * w; reroot(v, u, n); } }; dfs(0, -1); reroot(0, -1, subtreeSize[0]); cout << "最佳位置: " << bestLocation << " 最小总距离: " << minTotalDist << endl; }

4. 实战演练与常见陷阱

4.1 典型测试用例设计

1. 基础验证用例

   3 1 2 2 3

   预期直径：2（路径1-2-3）

2. 多分支复杂树

   7 1 2 1 3 1 4 2 5 2 6 3 7

   预期直径：4（如路径5-2-1-3-7）

3. 含负权边树

   4 1 2 5 1 3 -2 3 4 8

   预期直径：11（路径2-1-3-4）

4.2 常见错误与调试技巧

1. 递归栈溢出：对于深度较大的树，递归实现可能导致栈溢出。可以改用迭代DFS或设置编译器栈大小。

2. 父节点检查遗漏：忘记跳过父节点会导致无限循环。确保每次递归都传递父节点信息。

3. 负权边处理不当：在两次DFS法中未检查边权正负，导致错误结果。使用前务必确认问题约束。

4. 初始状态设置错误：在树形DP中，忘记初始化d1和d2数组会导致计算错误。

// 迭代DFS实现示例（避免递归栈溢出） void iterativeDFS(int start, vector<int>& distances, const vector<vector<int>>& tree) { stack<pair<int, int>> s; // {node, parent} s.push({start, -1}); distances[start] = 0; while (!s.empty()) { auto [u, fa] = s.top(); s.pop(); for (int v : tree[u]) { if (v != fa && distances[v] == -1) { distances[v] = distances[u] + 1; s.push({v, u}); } } } }

在实际编码面试中，建议先明确说明方法选择理由（如"因为题目保证边权为正，我选择实现更简单的两次DFS法"），然后逐步实现并验证边界条件。