供应链最高价问题的树形遍历与动态规划解法

1. 供应链最高价问题解析

供应链最高价问题是一个典型的树形结构遍历与动态规划结合的算法题目。题目通常描述为：给定一个供应链网络（以树的形式表示），每个节点代表一个供应商，根节点是制造商，叶子节点是零售商。每个节点会以一定比率（r）加价采购价格。我们需要找出所有零售商中的最高售价。

这个问题的核心在于理解供应链加价机制。假设根节点（制造商）的初始价格为P，当产品从父节点传递到子节点时，每个中间商会在进货价基础上加价r%。因此，一个深度为d的零售商最终售价为 P*(1+r)^d。

关键点：供应链加价是复合增长的典型场景，与银行复利计算原理相同。

2. 数据结构设计与输入处理

2.1 树形结构存储方案

在C++中表示树结构通常有三种选择：

1. 指针表示的动态节点（适合复杂树操作）
2. 邻接表（适合稀疏树）
3. 父指针数组（本题最佳选择）

vector<int> parent; // 父节点索引 vector<vector<int>> children; // 子节点列表

输入处理示例：

int n; double p, r; cin >> n >> p >> r; parent.resize(n); children.resize(n); for(int i=0; i<n; i++){ cin >> parent[i]; if(parent[i] != -1){ children[parent[i]].push_back(i); } }

2.2 输入的特殊情况处理

需要注意的边界条件：

• 空供应链（n=0）
• 单节点供应链（n=1）
• 所有节点都是零售商的情况（children全空）

3. 深度优先搜索实现

3.1 递归DFS实现

double max_price = p; int max_depth = 0; void dfs(int node, int depth){ if(children[node].empty()){ // 叶子节点 double current_price = p * pow(1+r/100, depth); if(current_price > max_price){ max_price = current_price; max_depth = depth; } return; } for(int child : children[node]){ dfs(child, depth+1); } }

3.2 迭代DFS实现（避免栈溢出）

stack<pair<int,int>> s; // <节点索引, 当前深度> s.push({root, 0}); while(!s.empty()){ auto [node, depth] = s.top(); s.pop(); if(children[node].empty()){ double current_price = p * pow(1+r/100, depth); // ...更新最大值... } for(auto it = children[node].rbegin(); it != children[node].rend(); ++it){ s.push({*it, depth+1}); } }

4. 广度优先搜索方案

4.1 标准BFS实现

queue<pair<int,int>> q; // <节点索引, 当前深度> q.push({root, 0}); while(!q.empty()){ auto [node, depth] = q.front(); q.pop(); if(children[node].empty()){ // ...价格计算... } for(int child : children[node]){ q.push({child, depth+1}); } }

4.2 层级统计优化

当只需要知道最大深度时，可以优化为：

int depth = 0; int count = q.size(); // 当前层节点数 while(!q.empty()){ int node = q.front(); q.pop(); if(children[node].empty()){ max_depth = max(max_depth, depth); } for(int child : children[node]){ next_level.push(child); } if(--count == 0){ depth++; count = next_level.size(); swap(q, next_level); } }

5. 性能优化技巧

5.1 数学公式优化

避免重复计算pow：

// 预计算所有可能的深度 vector<double> price_table(max_possible_depth+1); for(int i=0; i<=max_possible_depth; i++){ price_table[i] = p * pow(1+r/100, i); }

5.2 记忆化搜索

对于大规模树结构：

vector<int> depth_memo(n, -1); int get_depth(int node){ if(depth_memo[node] != -1) return depth_memo[node]; if(parent[node] == -1) return 0; return depth_memo[node] = get_depth(parent[node]) + 1; }

6. 完整解决方案代码

#include <iostream> #include <vector> #include <cmath> #include <queue> using namespace std; int main() { int n; double p, r; cin >> n >> p >> r; vector<vector<int>> children(n); int root = -1; for(int i=0; i<n; i++){ int parent; cin >> parent; if(parent == -1){ root = i; }else{ children[parent].push_back(i); } } queue<pair<int,int>> q; q.push({root, 0}); double max_price = p; int max_depth = 0, count = 0; while(!q.empty()){ auto [node, depth] = q.front(); q.pop(); if(children[node].empty()){ double current_price = p * pow(1+r/100, depth); if(current_price > max_price){ max_price = current_price; max_depth = depth; count = 1; }else if(current_price == max_price){ count++; } } for(int child : children[node]){ q.push({child, depth+1}); } } printf("%.2f %d", max_price, count); return 0; }

7. 常见问题与调试技巧

7.1 浮点数精度问题

比较浮点数时的正确方式：

const double EPS = 1e-8; if(fabs(a - b) < EPS){ // 视为相等 }

7.2 输入格式错误处理

if(cin.fail()){ cerr << "Invalid input format" << endl; return 1; }

7.3 内存泄漏检查

对于动态分配的树节点：

struct TreeNode{ int val; vector<TreeNode*> children; ~TreeNode(){ for(auto child : children){ delete child; } } };

8. 复杂度分析与优化验证

8.1 时间复杂度

• DFS/BFS：O(n) 每个节点访问一次
• 空间复杂度：O(n) 存储树结构

8.2 测试用例设计

典型测试场景：

1. 单链结构（最坏情况）
2. 完全二叉树
3. 星型结构（一个根多个叶子）
4. 大规模随机树（1e5节点）

9. 实际应用扩展

9.1 多级经销商价格计算

实际业务中可能需要：

struct Node{ double base_price; vector<pair<int, double>> children; // <节点索引, 加价比例> };

9.2 可视化输出

生成树形结构图：

void print_tree(int node, int indent=0){ cout << string(indent, ' ') << node << endl; for(int child : children[node]){ print_tree(child, indent+2); } }

10. 工程实践建议

1. 使用智能指针管理树节点内存
2. 对大规模数据采用内存映射文件
3. 添加输入数据合法性校验
4. 实现单元测试框架验证核心算法

void test_case(){ // 构建测试树 // 调用算法 // 验证结果 }

11. 性能对比实验

测试不同实现方式的耗时（单位：ms）：

12. 代码风格与规范

1. 使用有意义的变量名
2. 添加必要的注释
3. 函数不超过50行
4. 避免全局变量
5. 错误处理使用异常

try{ // 可能出错的操作 }catch(const exception& e){ cerr << "Error: " << e.what() << endl; }

13. 多语言实现对比

Python实现示例：

from collections import deque def find_max_price(n, p, r, parents): children = [[] for _ in range(n)] root = -1 for i, parent in enumerate(parents): if parent == -1: root = i else: children[parent].append(i) q = deque([(root, 0)]) max_price = p max_depth = 0 while q: node, depth = q.popleft() if not children[node]: current_price = p * (1 + r/100) ** depth if current_price > max_price: max_price = current_price max_depth = depth for child in children[node]: q.append((child, depth+1)) return max_price, max_depth

14. 算法竞赛技巧

1. 使用快速输入输出：

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

2. 预编译常用头文件：

#include <bits/stdc++.h>

3. 使用宏简化代码：

#define REP(i,n) for(int i=0; i<(n); i++)

15. 相关算法扩展

1. 树的重心问题
2. 树的直径计算
3. 最近公共祖先(LCA)
4. 树链剖分
5. 树上差分

// 计算树直径示例 pair<int,int> dfs_diameter(int u, int parent){ int max_depth1 = 0, max_depth2 = 0; int diameter = 0; for(int v : children[u]){ if(v == parent) continue; auto [depth, sub_diameter] = dfs_diameter(v, u); diameter = max(diameter, sub_diameter); if(depth >= max_depth1){ max_depth2 = max_depth1; max_depth1 = depth; }else if(depth > max_depth2){ max_depth2 = depth; } } diameter = max(diameter, max_depth1 + max_depth2); return {max_depth1 + 1, diameter}; }