1. 題目鏈接

2646. 最小化旅行的價格總和 - 力扣（LeetCode）

2. 題目描述

現有一棵無向、無根的樹，樹中有 n 個節點，按從 0 到 n - 1 編號。給你一個整數 n 和一個長度為 n - 1 的二維整數數組 edges ，其中 edges[i] = [ai, bi] 表示樹中節點 ai 和 bi 之間存在一條邊。

每個節點都關聯一個價格。給你一個整數數組 price ，其中 price[i] 是第 i 個節點的價格。

給定路徑的 價格總和 是該路徑上所有節點的價格之和。

另給你一個二維整數數組 trips ，其中 trips[i] = [starti, endi] 表示您從節點 starti 開始第 i 次旅行，并通過任何你喜歡的路徑前往節點 endi 。

在執行第一次旅行之前，你可以選擇一些 非相鄰節點 并將價格減半。

返回執行所有旅行的最小價格總和。

3. 題目示例

示例 1 :

輸入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
輸出：23
解釋：
上圖表示將節點 2 視為根之后的樹結構。第一個圖表示初始樹，第二個圖表示選擇節點 0 、2 和 3 并使其價格減半后的樹。
第 1 次旅行，選擇路徑 [0,1,3] 。路徑的價格總和為 1 + 2 + 3 = 6 。
第 2 次旅行，選擇路徑 [2,1] 。路徑的價格總和為 2 + 5 = 7 。
第 3 次旅行，選擇路徑 [2,1,3] 。路徑的價格總和為 5 + 2 + 3 = 10 。
所有旅行的價格總和為 6 + 7 + 10 = 23 。可以證明，23 是可以實現的最小答案。

示例 2 :

輸入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
輸出：1
解釋：
上圖表示將節點 0 視為根之后的樹結構。第一個圖表示初始樹，第二個圖表示選擇節點 0 并使其價格減半后的樹。 
第 1 次旅行，選擇路徑 [0] 。路徑的價格總和為 1 。 
所有旅行的價格總和為 1 。可以證明，1 是可以實現的最小答案。

4. 解題思路

1. 問題理解：
   • 給定一棵樹，每個節點有一個價格。
   • 多個旅行路徑（trips），每個路徑從起點到終點。
   • 可以選擇將某些節點的價格減半，但相鄰節點不能同時減半。
   • 目標是最小化所有旅行路徑的總價格。
2. 關鍵步驟：
   • 統計節點訪問次數：通過DFS遍歷每個trip的路徑，統計每個節點被訪問的次數。
   • 動態規劃計算最小總價格：類似"打家劫舍III"問題，對每個節點有兩種選擇（減半或不變），需要滿足相鄰節點不能同時減半的條件。
3. DFS統計訪問次數：
   • 對每個trip，從起點DFS到終點，標記路徑上的所有節點。
   • 使用cnt數組記錄每個節點被訪問的總次數。
4. 動態規劃設計：
   • 狀態定義：dp(x)返回一個數組[notHalve, halve]，表示節點x不減半或減半時的最小總價格。
   • 狀態轉移：
     • 如果x不減半，子節點可以減半或不變，取最小值。
     • 如果x減半，子節點必須不減半。
   • 初始化：葉子節點的notHalve和halve直接計算。

5. 題解代碼

class Solution {private List<Integer>[] g;  // 鄰接表存儲樹結構private int[] price, cnt;    // price: 節點價格數組, cnt: 節點訪問次數數組private int end;             // 當前trip的目標節點public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {// 初始化鄰接表g = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());for (int[] e : edges) {int x = e[0], y = e[1];g[x].add(y);g[y].add(x);}// 初始化節點訪問次數數組cnt = new int[n];// 處理每個trip，統計路徑上的節點訪問次數for (int[] t : trips) {end = t[1];dfs(t[0], -1);}this.price = price;// 動態規劃計算最小總價格int[] res = dp(0, -1);return Math.min(res[0], res[1]);}// DFS統計trip路徑上的節點訪問次數private boolean dfs(int x, int fa) {if (x == end) {cnt[x]++;return true; // 找到目標節點}for (int y : g[x]) {if (y != fa && dfs(y, x)) {cnt[x]++; // 當前節點在路徑上return true;}}return false; // 未找到目標節點}// 動態規劃計算最小總價格（類似打家劫舍III）private int[] dp(int x, int fa) {int notHalve = price[x] * cnt[x]; // 當前節點價格不減半的總價格int halve = notHalve / 2;         // 當前節點價格減半的總價格for (int y : g[x]) {if (y != fa) {int[] res = dp(y, x); // 子節點的計算結果notHalve += Math.min(res[0], res[1]); // 當前節點不減半，子節點可以減半或不變halve += res[0]; // 當前節點減半，子節點必須不變}}return new int[]{notHalve, halve};}
}

6. 復雜度分析

時間復雜度：

• DFS統計訪問次數：O(n * m)，其中n是節點數，m是trip數量（每個trip最壞O(n)）。
• 動態規劃：O(n)，每個節點處理一次。
• 總時間復雜度：O(n * m + n) = O(n * m)。

空間復雜度：

• 鄰接表：O(n)。
• cnt數組：O(n)。
• 遞歸調用棧：最壞O(n)。
• 總空間復雜度：O(n)。