蓝桥杯树的直径求解与旅费计算实战

1. 题目背景与问题解析

这道题目来自蓝桥杯2013年省赛A组，考察的是图论中的经典问题——树的直径求解。题目描述了一位大臣需要在不同城市间旅行，旅费与距离成正比。我们需要找到两个城市间最长的路径，计算出对应的旅费。

1.1 题目核心需求

题目给出一个树形结构的城市网络（n个城市，n-1条道路），要求：

1. 找出距离最远的两个城市（即树的直径）
2. 根据距离计算旅费（距离d的旅费公式为d×10 + (1+2+...+d)）

1.2 解题思路分析

由于城市网络是树结构（无环连通图），求最长路径就是求树的直径。常见解法有：

• 两次DFS/BFS：时间复杂度O(n)
• 树形DP：时间复杂度O(n)

本题适合采用DFS实现，因为：

1. 数据规模n≤1e4，O(n)算法完全可行
2. DFS递归实现代码简洁，适合竞赛场景
3. 可以顺便练习图的深度优先遍历

2. 算法设计与实现细节

2.1 树的直径求解原理

树的直径定义为树上最长路径的长度。关键性质：

• 从任意节点出发，找到的最远节点一定是直径的一个端点
• 再从该端点出发，找到的最远节点就是另一个端点

基于此性质，我们可以：

1. 任选一个起点（如城市1）进行DFS，找到最远城市u
2. 从城市u出发再次DFS，找到最远城市v
3. u-v的路径就是树的直径

2.2 图的存储与遍历

采用邻接表存储图结构（比邻接矩阵更节省空间）：

vector<pair<int,int>> adj[MAXN]; // adj[u] = {v, w}

DFS实现要点：

1. 需要记录访问状态避免重复访问
2. 需要维护当前路径长度
3. 需要更新最大距离及对应节点

核心DFS函数框架：

void dfs(int u, int fa, int dist, int& max_dist, int& far_node) { if(dist > max_dist) { max_dist = dist; far_node = u; } for(auto [v,w] : adj[u]) { if(v != fa) { dfs(v, u, dist + w, max_dist, far_node); } } }

2.3 旅费计算公式优化

题目给出的旅费公式为： 费用 = d×10 + (1+2+...+d) = 10d + d(d+1)/2

可以预先计算保存结果，避免重复计算：

int calc_cost(int d) { return 10 * d + d * (d + 1) / 2; }

3. 完整代码实现与注释

#include <iostream> #include <vector> #include <utility> using namespace std; const int MAXN = 1e4 + 5; vector<pair<int,int>> adj[MAXN]; void dfs(int u, int fa, int dist, int& max_dist, int& far_node) { if(dist > max_dist) { max_dist = dist; far_node = u; } for(auto [v,w] : adj[u]) { if(v != fa) { dfs(v, u, dist + w, max_dist, far_node); } } } int calc_cost(int d) { return 10 * d + d * (d + 1) / 2; } int main() { int n; cin >> n; // 构建邻接表 for(int i=1; i<n; ++i) { int u, v, w; cin >> u >> v >> w; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } // 第一次DFS找直径端点u int max_dist = 0, u = 1; dfs(1, -1, 0, max_dist, u); // 第二次DFS找直径端点v并得到直径长度 max_dist = 0; int v = u; dfs(u, -1, 0, max_dist, v); // 计算旅费 cout << calc_cost(max_dist) << endl; return 0; }

4. 关键问题与优化技巧

4.1 常见错误排查

1. 栈溢出问题：

   • 当n=1e4时，DFS递归深度可能达到1e4
   • 解决方法：调整栈大小（竞赛中通常允许）或改用非递归DFS

2. 输入处理错误：

   • 注意城市编号是否从0或1开始
   • 边是无向的，邻接表需要添加双向边

3. 初始化问题：

   • 每次DFS前要重置max_dist
   • 访问标记可以用fa参数代替vis数组

4.2 性能优化建议

1. 输入输出加速：

   ios::sync_with_stdio(false); cin.tie(0);

2. 内存优化：

   • 使用vector.clear()复用邻接表
   • 对于固定大小的图，可以用静态数组替代vector

3. 算法替代方案：

   • 需要多次查询时，可以预处理各点深度
   • 考虑使用BFS实现，避免递归开销

5. 竞赛应用与扩展思考

5.1 类似题型训练建议

1. 基础变式：

   • POJ 2631 - Roads in the North（纯求树的直径）
   • LeetCode 1245 - Tree Diameter（无权重树）

2. 进阶应用：

   • 带权树的直径应用（如本题）
   • 动态树直径维护问题
   • 多棵树的直径比较

5.2 实际应用场景

1. 网络拓扑设计：

   • 计算机网络中的最远节点延迟计算
   • 分布式系统中的通信成本估算

2. 交通规划：

   • 城市间最长运输路线规划
   • 物流配送的最远站点识别

3. 游戏开发：

   • 游戏地图中最远两点距离计算
   • NPC巡逻路线规划

5.3 算法扩展思考

1. 动态树直径问题：

   • 如何支持动态加边/删边操作
   • 使用LCT（Link-Cut Tree）维护

2. 多直径处理：

   • 当树中存在多条最长路径时的处理
   • 记录所有直径端点的方法

3. 其他图结构：

   • 一般图中最长路径是NP难问题
   • 特殊图类（如仙人掌图）的直径求解

提示：在竞赛中遇到树结构问题时，优先考虑DFS/BFS遍历。树的直径问题通常作为图论的基础应用出现，掌握两次遍历法可以解决大部分变式题目。实际编码时要注意树的存储方式和遍历的终止条件。