DeepSeek LeetCode 2646. 最小化旅行的价格总和 C++实现

以下是 LeetCode 2646“最小化旅行的价格总和”的 C++ 实现，思路与 Java 版本一致，采用 DFS 统计节点访问次数 + 树形 DP。

C++ 代码

```cpp
class Solution {
vector<vector<int>> graph;
vector<int> price;
vector<int> count;

// 返回是否存在从 u 到 target 的路径，若存在则累加沿途节点的 count
bool dfsCount(int u, int parent, int target) {
if (u == target) {
count[u]++;
return true;
}
for (int v : graph[u]) {
if (v != parent && dfsCount(v, u, target)) {
count[u]++;
return true;
}
}
return false;
}

// 返回 pair: first = 当前节点不半价的最小总价, second = 当前节点半价的最小总价
pair<int, int> dfs(int u, int parent) {
int notHalf = price[u] * count[u]; // 当前节点不半价
int half = price[u] * count[u] / 2; // 当前节点半价

for (int v : graph[u]) {
if (v == parent) continue;
auto [childNotHalf, childHalf] = dfs(v, u);
notHalf += min(childNotHalf, childHalf); // 父不半价，子可选最优
half += childNotHalf; // 父半价，子必须不半价
}
return {notHalf, half};
}

public:
int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
this->price = price;
graph.resize(n);
for (auto& e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}

count.assign(n, 0);
for (auto& trip : trips) {
dfsCount(trip[0], -1, trip[1]);
}

auto [rootNotHalf, rootHalf] = dfs(0, -1);
return min(rootNotHalf, rootHalf);
}
};
```

代码说明

1. 统计访问次数
dfsCount 函数递归查找从 start 到 end 的路径，并将路径上所有节点的 count 加 1。
2. 树形 DP
dfs 函数返回 pair<int,int>：
· first：当前节点 不半价 时，子树的最小总代价
· second：当前节点 半价 时，子树的最小总代价
3. 状态转移
· 当前节点不半价 → 子节点可以半价或不半价，取 min
· 当前节点半价 → 子节点 必须不半价
4. 最终答案
对根节点取 min(不半价, 半价)

复杂度分析

· 时间：O(n * m)，n 为节点数，m 为路径数（最坏情况每条路径遍历整棵树）
· 空间：O(n)，递归栈 + 邻接表

优化提示

如果数据规模较大（例如 n, m <= 10^5），可以使用 LCA + 差分数组 优化路径统计，将单次路径复杂度降为 O(log n)。需要我提供这个优化版本吗？