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

这是 LeetCode 第 2646 题“最小化旅行的价格总和”的 Java 实现，核心思路是 DFS + 树形动态规划。

解题思路

1. 统计节点访问次数：对于每条路径 (start, end)，通过 DFS 找到路径并累加该路径上所有节点的访问次数。
2. 定义 DP 状态：对每个节点 u：
· dp[u][0]：不半价时，以 u 为根的子树的最小总代价
· dp[u][1]：半价时，以 u 为根的子树的最小总代价
3. 状态转移：如果 u 半价，则子节点不能半价；如果 u 不半价，子节点可以半价或不半价，取较小值。
4. 最终结果：min(dp[root][0], dp[root][1])

Java 代码

```java
class Solution {
List<Integer>[] graph;
int[] price;
int[] count; // 每个节点被访问的次数

public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
this.price = price;
graph = new List[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int[] e : edges) {
graph[e[0]].add(e[1]);
graph[e[1]].add(e[0]);
}

count = new int[n];
for (int[] trip : trips) {
// 统计路径上的节点次数
dfsCount(trip[0], -1, trip[1]);
}

int[] res = dfs(0, -1);
return Math.min(res[0], res[1]);
}

// 返回从 u 到 target 的路径是否存在，若存在则累加沿途节点
private boolean 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;
}

// 返回 int[2]: 0-不半价最小总价, 1-半价最小总价
private 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;
int[] childRes = dfs(v, u);
notHalf += Math.min(childRes[0], childRes[1]); // 父不半价，子可选
half += childRes[0]; // 父半价，子必须不半价
}
return new int[]{notHalf, half};
}
}
```

复杂度分析

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

优化建议（可选）

如果 n 和 m 都很大，可以先用 LCA（最近公共祖先） 优化路径统计，将 dfsCount 的 O(n) 单次路径降为 O(log n)，总复杂度变为 O((n + m) log n)。本题数据规模较小，上述解法已足够。

需要我给出 LCA 优化的版本吗？