# 2646. 最小化旅行的价格总和 (Hard)

## 问题描述
[2646. 最小化旅行的价格总和 (Hard)](https://leetcode.cn/problems/minimize-the-total-price-of-the-trips/)
现有一棵无向、无根的树，树中有 `n` 个节点，按从 `0` 到 `n - 
1` 编号。给你一个整数 `n` 和一个长度为 `n - 1` 的二维整数数
组 `edges` ，其中 `edges[i] = [aᵢ, bᵢ]` 表示树中节点 `aᵢ` 和
`bᵢ` 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 `price` ，其中 `pri
ce[i]` 是第 `i` 个节点的价格。

给定路径的 **价格总和** 是该路径上所有节点的价格之和。

另给你一个二维整数数组 `trips` ，其中 `trips[i] = [startᵢ, e
ndᵢ]` 表示您从节点 `startᵢ` 开始第 `i` 次旅行，并通过任何你
喜欢的路径前往节点 `endᵢ` 。

在执行第一次旅行之前，你可以选择一些 **非相邻节点** 并将价格
减半。

返回执行所有旅行的最小价格总和。

**示例 1：**

![](https://assets.leetcode.com/uploads/2023/03/16/diagram2.
png)

```
输入：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：**

![](https://assets.leetcode.com/uploads/2023/03/16/diagram3.
png)

```
输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出：1
解释：
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第
二个图表示选择节点 0 并使其价格减半后的树。
第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。
所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。

```

**提示：**

- `1 <= n <= 50`
- `edges.length == n - 1`
- `0 <= aᵢ, bᵢ <= n - 1`
- `edges` 表示一棵有效的树
- `price.length == n`
- `price[i]` 是一个偶数
- `1 <= price[i] <= 1000`
- `1 <= trips.length <= 100`
- `0 <= startᵢ, endᵢ <= n - 1`

## 解题思路
贡献法 + 树上 dp

首先，对每条路径，在树上所有结点的价格已经确定的情况下，由于树是不存在环的，那么从起点到终点的非重复路径是唯一的，而这一最短路径必定对应着最小的路径价格。

因此，我们需要遍历 `trip`，并对树上每个结点，标记它一共被经过了多少次。

然后便是树上 dp 的思想了，即枚举当前结点选或不选两种情况，划分为更简单的子问题，从而可以递归解决，这里的返回值最好是 `pair<int, int>`，一个表示当前结点价格减半的最小价格之和，一个表示不减半的价格之和。

对于树的遍历，由于不存在环，我们不需要使用 `vis` 数组进行标记，只需要在 `dfs` 函数中添加一个参数表示其父结点就可以了。

## 代码
```cpp
class Solution {
  public:
    // 寻找不重复路径
    void dfs(int cur, int end, vector<int> &path, vector<vector<int>> &graph, vector<bool> &vis, vector<vector<int>> &all_path) {
        if (cur == end) {
            all_path.push_back(path);
            return;
        }
        for (auto next : graph[cur]) {
            if (!vis[next]) {
                path.push_back(next);
                vis[next] = true;
                dfs(next, end, path, graph, vis, all_path);
                path.pop_back();
                vis[next] = false;
            }
        }
    }
    pair<int, int> GetRes(vector<vector<int>> &graph, vector<int> &times, int fa, int idx, vector<int> &price) {
        // 如何避免重复？
        int half = price[idx] * times[idx] / 2, not_half = price[idx] * times[idx];
        for (auto next : graph[idx]) {
            if (next == fa) {
                continue;
            }
            auto [sum_half, sum_not_half] = GetRes(graph, times, idx, next, price);
            half += sum_not_half; // next 不能减半了
            not_half += min(sum_half, sum_not_half);
        }
        return {half, not_half};
    }
    int minimumTotalPrice(int n, vector<vector<int>> &edges, vector<int> &price, vector<vector<int>> &trips) {
        // 统计每个结点的贡献，即每个结点会被经过多少次
        vector<int> times(n);
        vector<vector<int>> graph(n);
        for (int i = 0; i < edges.size(); ++i) {
            int x = edges[i][0], y = edges[i][1];
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        
        vector<vector<int>> all_path;
        for (auto &vec : trips) {
            int start = vec[0], end = vec[1];
            vector<int> path;
            vector<bool> vis(n);
            vis[start] = true;
            path.push_back(start);
            dfs(start, end, path, graph, vis, all_path);
        }
        vector<int> cnt(n);
        for (const auto &path_ : all_path) {
            for (int idx : path_) {
                ++times[idx];
            }
        }
        auto [half, not_half] = GetRes(graph, times, 0, 0, price);
        return min(half, not_half);
    }
};
```