别再死记模板！用两种方法（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关键参数说明参数类型作用uint当前访问节点faint父节点避免回访depthint当前累计深度maxDepthint记录最大深度引用传递farthestNodeint记录最远节点引用传递1.2 算法实现与复杂度分析完整的两步DFS实现如下pairint, int findDiameterDFS(vectorvectorint tree) { int n tree.size(); int end1 0, maxDepth 0; // 第一次DFS从任意节点这里选0找到最远节点end1 functionvoid(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; }; vectorvectorEdge adj; vectorint d1, d2; int diameter; void computeDiameter() { int n adj.size(); d1.assign(n, 0); d2.assign(n, 0); diameter 0; functionvoid(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状态转移分析情况处理方式示例场景新路径 d1d2继承d1d1更新发现更长分支d1 新路径 d2仅更新d2发现新的次长分支新路径 d2忽略非关键路径3. 两种方法的深度对比与选择策略3.1 性能与适用场景对比表DFS与DP方法对比特性两次DFS法树形DP法时间复杂度O(n)O(n)空间复杂度O(n)O(n)负权边支持不支持支持实现难度较简单中等额外信息仅直径长度各子树深度信息适用场景无权树或正权树所有类型树3.2 典型应用场景分析网络延迟分析在计算机网络中树的直径可以反映最坏情况下的通信延迟。如果边权表示延迟时间必须使用树形DP法。社交网络影响传播在社交网络树形结构中直径两端的人物通常是信息传播的关键节点。此时使用两次DFS法更高效。资源分配优化如医院选址问题需要同时考虑树的重心和直径特性这时树形DP法能提供更多子树信息。// 医院选址问题中的综合应用示例 void findOptimalLocation(vectorvectorEdge tree, vectorint population) { vectorint totalDist(tree.size(), 0); vectorint subtreeSize(tree.size(), 0); int minTotalDist INT_MAX; int bestLocation 0; functionvoid(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; } }; functionvoid(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 典型测试用例设计基础验证用例3 1 2 2 3预期直径2路径1-2-3多分支复杂树7 1 2 1 3 1 4 2 5 2 6 3 7预期直径4如路径5-2-1-3-7含负权边树4 1 2 5 1 3 -2 3 4 8预期直径11路径2-1-3-44.2 常见错误与调试技巧递归栈溢出对于深度较大的树递归实现可能导致栈溢出。可以改用迭代DFS或设置编译器栈大小。父节点检查遗漏忘记跳过父节点会导致无限循环。确保每次递归都传递父节点信息。负权边处理不当在两次DFS法中未检查边权正负导致错误结果。使用前务必确认问题约束。初始状态设置错误在树形DP中忘记初始化d1和d2数组会导致计算错误。// 迭代DFS实现示例避免递归栈溢出 void iterativeDFS(int start, vectorint distances, const vectorvectorint tree) { stackpairint, 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法然后逐步实现并验证边界条件。