# Minimize the Total Price of the Trips
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimize-the-total-price-of-the-trips)
Canonical: https://scaleengineer.com/dsa/problems/minimize-the-total-price-of-the-trips
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Tree, Graph
---
## Problem
There exists an undirected and unrooted tree with `n` nodes indexed from `0` to `n - 1`. You are given the integer `n` and a 2D integer array `edges` of length `n - 1`, where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the tree.

Each node has an associated price. You are given an integer array `price`, where `price[i]` is the price of the `ith` node.

The **price sum** of a given path is the sum of the prices of all nodes lying on that path.

Additionally, you are given a 2D integer array `trips`, where `trips[i] = [starti, endi]` indicates that you start the `ith` trip from the node `starti` and travel to the node `endi` by any path you like.

Before performing your first trip, you can choose some **non-adjacent** nodes and halve the prices.

Return _the minimum total price sum to perform all the given trips_.

**Example 1:**

![](https://assets.glich.co/dsa/minimize-the-total-price-of-the-trips/image0.png) 

**Input:** n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
**Output:** 23
**Explanation:** The diagram above denotes the tree after rooting it at node 2. The first part shows the initial tree and the second part shows the tree after choosing nodes 0, 2, and 3, and making their price half.
For the 1st trip, we choose path [0,1,3]. The price sum of that path is 1 + 2 + 3 = 6.
For the 2nd trip, we choose path [2,1]. The price sum of that path is 2 + 5 = 7.
For the 3rd trip, we choose path [2,1,3]. The price sum of that path is 5 + 2 + 3 = 10.
The total price sum of all trips is 6 + 7 + 10 = 23.
It can be proven, that 23 is the minimum answer that we can achieve.

**Example 2:**

![](https://assets.glich.co/dsa/minimize-the-total-price-of-the-trips/image1.png) 

**Input:** n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
**Output:** 1
**Explanation:** The diagram above denotes the tree after rooting it at node 0. The first part shows the initial tree and the second part shows the tree after choosing node 0, and making its price half.
For the 1st trip, we choose path [0]. The price sum of that path is 1.
The total price sum of all trips is 1. It can be proven, that 1 is the minimum answer that we can achieve.

**Constraints:**

* `1 <= n <= 50`
* `edges.length == n - 1`
* `0 <= ai, bi <= n - 1`
* `edges` represents a valid tree.
* `price.length == n`
* `price[i]` is an even integer.
* `1 <= price[i] <= 1000`
* `1 <= trips.length <= 100`
* `0 <= starti, endi <= n - 1`

# Approaches
## Brute Force by Enumerating All Subsets
This approach breaks the problem into two parts. First, it calculates how many times each node is part of a trip path. Then, it tries every possible subset of nodes to halve their prices. For each subset, it checks if it's valid (no two nodes are adjacent) and calculates the total price. The minimum price over all valid subsets is the answer.
**Time:** O(T*n + 2^n * n^2), where T is the number of trips and n is the number of nodes. Calculating counts takes O(T*n). The brute-force search involves checking 2^n subsets, and for each, validating its independence takes O(n^2) in the worst case. This complexity is dominated by the exponential term. · **Space:** O(n) to store the adjacency list, counts, and the current subset being processed.
**Pros:** Conceptually simple and follows the problem statement directly.
**Cons:** Extremely inefficient due to its exponential time complexity.; Not feasible for the given constraints (`n` up to 50), and will result in a Time Limit Exceeded error.
### Explanation
The first step is to determine the total number of times each node is visited across all trips. This can be done by iterating through each trip, finding the path, and incrementing a counter for each node on that path. Once we have these counts, the problem becomes about selecting a set of non-adjacent nodes to halve their prices to achieve the maximum possible total price reduction.

This approach tackles the selection problem with brute force. It systematically generates every single subset of the `n` nodes. For each subset, it first verifies if it's an 'independent set'—a set where no two nodes are neighbors. If the subset is valid, it calculates the total price reduction it offers. By comparing the reductions from all valid subsets, it finds the maximum possible reduction. The final answer is the original total price minus this maximum reduction.

```java
// This snippet demonstrates the brute-force part of the solution.
// It assumes that the adjacency list `adj`, the `price` array, and the `counts` array
// (calculated from all trips) are already available.

public long findMaxReductionBruteForce(int n, List<List<Integer>> adj, int[] price, int[] counts) {
    long maxReduction = 0;

    // Iterate through all 2^n subsets of nodes using a bitmask
    for (int i = 0; i < (1 << n); i++) {
        List<Integer> subset = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) != 0) {
                subset.add(j);
            }
        }

        // Check if the subset is an independent set (no two nodes are adjacent)
        boolean isIndependent = true;
        if (subset.size() > 1) {
            for (int u_idx = 0; u_idx < subset.size(); u_idx++) {
                for (int v_idx = u_idx + 1; v_idx < subset.size(); v_idx++) {
                    int u = subset.get(u_idx);
                    int v = subset.get(v_idx);
                    boolean connected = false;
                    for (int neighbor : adj.get(u)) {
                        if (neighbor == v) {
                            connected = true;
                            break;
                        }
                    }
                    if (connected) {
                        isIndependent = false;
                        break;
                    }
                }
                if (!isIndependent) break;
            }
        }

        // If it's an independent set, calculate the reduction and update the max
        if (isIndependent) {
            long currentReduction = 0;
            for (int node : subset) {
                currentReduction += (long)price[node] / 2 * counts[node];
            }
            maxReduction = Math.max(maxReduction, currentReduction);
        }
    }
    return maxReduction;
}
```
### Algorithm
- **Step 1: Calculate Node Visit Frequencies.**
  - Build an adjacency list representation of the tree from the `edges` array.
  - Initialize a `counts` array of size `n` to all zeros.
  - For each trip `[start, end]` in `trips`:
    - Find the unique path from `start` to `end` using a traversal like Breadth-First Search (BFS). This can be done by keeping track of parent pointers during the traversal and then backtracking from `end` to `start`.
    - For each node on the path, increment its corresponding value in the `counts` array.
- **Step 2: Brute-Force Search for Optimal Set.**
  - Calculate the total price without any reductions: `initial_total_price = sum(price[i] * counts[i])` for all `i`.
  - The goal is to find a set of non-adjacent nodes `S` that maximizes the total reduction: `sum_{i in S} (price[i] / 2 * counts[i])`.
  - Iterate through all `2^n` possible subsets of nodes. A bitmask from `0` to `2^n - 1` can represent all subsets.
  - For each subset:
    - Check if it's a valid independent set, meaning no two nodes in the subset are connected by an edge.
    - If it is valid, calculate the price reduction for this subset.
    - Keep track of the maximum reduction found among all valid subsets.
- **Step 3: Compute Final Price.**
  - The minimum total price is `initial_total_price - max_reduction`.

## Dynamic Programming on a Tree
This efficient approach also separates the problem into two main subproblems. The first, calculating node visit frequencies, is the same as in the brute-force method. The crucial improvement lies in the second subproblem: finding the optimal set of nodes to halve prices. Instead of exploring every possibility, this method uses dynamic programming on the tree. This technique is well-suited for optimization problems on tree structures and is equivalent to solving the 'Maximum Weight Independent Set' problem on our tree, where node weights are the potential price reductions.
**Time:** O(T*n + n), where T is the number of trips and n is the number of nodes. Calculating counts for all trips takes O(T*n). The dynamic programming part involves a single DFS traversal of the tree, which takes O(n). The total complexity is dominated by the count calculation. · **Space:** O(n) for the adjacency list, the `counts` array, parent pointers in BFS, and the recursion stack for DFS.
**Pros:** Highly efficient with a polynomial time complexity.; Guaranteed to find the optimal solution by correctly modeling the subproblem.; Handles the given constraints well.
**Cons:** More complex to understand and implement compared to a naive brute-force approach.; Requires knowledge of dynamic programming on trees.
### Explanation
First, we determine how many times each node is visited over all trips. We create a `counts` array and for each trip, we find the path (e.g., using BFS) and increment the count for each node on it. The total price without any discounts is `sum(price[i] * counts[i])`.

The core of this approach is to find the maximum possible price reduction. The reduction gained from halving the price of node `i` is `benefit[i] = (price[i] / 2) * counts[i]`. We must choose a set of non-adjacent nodes that maximizes the sum of their benefits. This is a classic DP problem on trees.

We perform a single DFS traversal from an arbitrary root. For each node `u`, we calculate two states:
1.  The maximum benefit from its subtree if we **halve** `u`'s price. In this case, we cannot halve the prices of its children.
2.  The maximum benefit from its subtree if we **do not halve** `u`'s price. In this case, for each child, we can choose whichever option (halving or not) yields a greater benefit for that child's subtree.

By computing these values for all nodes in a post-order traversal, we can determine the maximum total benefit for the entire tree. The final minimum price is the initial total price minus this maximum benefit.

```java
class Solution {
    private List<List<Integer>> adj;
    private int[] price;
    private int[] counts;

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

        counts = new int[n];
        for (int[] trip : trips) {
            findPathAndAddCount(trip[0], trip[1], n);
        }

        long initialTotalPrice = 0;
        for (int i = 0; i < n; i++) {
            initialTotalPrice += (long) price[i] * counts[i];
        }

        long[] result = dfs(0, -1);
        long maxBenefit = Math.max(result[0], result[1]);

        return (int) (initialTotalPrice - maxBenefit);
    }

    private void findPathAndAddCount(int start, int end, int n) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        boolean[] visited = new boolean[n];
        visited[start] = true;

        while (!q.isEmpty()) {
            int curr = q.poll();
            if (curr == end) break;
            for (int neighbor : adj.get(curr)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    parent[neighbor] = curr;
                    q.offer(neighbor);
                }
            }
        }

        int curr = end;
        while (curr != -1) {
            counts[curr]++;
            curr = parent[curr];
        }
    }

    // Returns a pair [max_benefit_without_halving_u, max_benefit_with_halving_u]
    private long[] dfs(int u, int p) {
        // dp[u][0]: max benefit from subtree at u, without halving price of u
        long benefitNotHalved = 0;
        // dp[u][1]: max benefit from subtree at u, with halving price of u
        long benefitHalved = (long) price[u] / 2 * counts[u];

        for (int v : adj.get(u)) {
            if (v == p) continue;
            long[] childResult = dfs(v, u);
            // If we don't halve u, we can choose the best option for child v
            benefitNotHalved += Math.max(childResult[0], childResult[1]);
            // If we halve u, we cannot halve child v
            benefitHalved += childResult[0];
        }

        return new long[]{benefitNotHalved, benefitHalved};
    }
}
```
### Algorithm
- **Step 1: Calculate Node Visit Frequencies.**
  - This step is identical to the brute-force approach. Build an adjacency list, and for each trip, find the path using BFS and increment the visit counts for nodes on the path in a `counts` array.
- **Step 2: Maximize Benefit with Dynamic Programming.**
  - The problem of selecting non-adjacent nodes to maximize a sum of values is the **Maximum Weight Independent Set** problem on a tree.
  - Define `benefit[i] = (price[i] / 2) * counts[i]`. We want to find an independent set `S` that maximizes `sum_{i in S} benefit[i]`.
  - Use Dynamic Programming on the tree. Root the tree arbitrarily (e.g., at node 0) and perform a single DFS traversal.
  - For each node `u`, we compute two values:
    - `dp[u][0]`: max benefit from `u`'s subtree if `u`'s price is **not** halved.
    - `dp[u][1]`: max benefit from `u`'s subtree if `u`'s price **is** halved.
  - The recurrence relations, computed in a post-order traversal fashion, are:
    - `dp[u][1] = benefit[u] + sum(dp[v][0])` for all children `v` of `u`. (If we take `u`, we cannot take its children).
    - `dp[u][0] = sum(max(dp[v][0], dp[v][1]))` for all children `v` of `u`. (If we don't take `u`, we can make the optimal choice for each child independently).
- **Step 3: Calculate Final Minimum Price.**
  - After the DFS from the root (e.g., node 0) is complete, the maximum total benefit is `max(dp[root][0], dp[root][1])`.
  - The final answer is `initial_total_price - max_benefit`.

# Solutions
### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  int[] price;
private
  int[] cnt;
public
  int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
    this.price = price;
    cnt = new int[n];
    g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    for (var e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    for (var t : trips) {
      int start = t[0], end = t[1];
      dfs(start, -1, end);
    }
    int[] ans = dfs2(0, -1);
    return Math.min(ans[0], ans[1]);
  }
private
  boolean dfs(int i, int fa, int k) {
    ++cnt[i];
    if (i == k) {
      return true;
    }
    boolean ok = false;
    for (int j : g[i]) {
      if (j != fa) {
        ok = dfs(j, i, k);
        if (ok) {
          break;
        }
      }
    }
    if (!ok) {
      --cnt[i];
    }
    return ok;
  }
private
  int[] dfs2(int i, int fa) {
    int a = cnt[i] * price[i];
    int b = a >> 1;
    for (int j : g[i]) {
      if (j != fa) {
        var t = dfs2(j, i);
        a += Math.min(t[0], t[1]);
        b += t[0];
      }
    }
    return new int[]{a, b};
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumTotalPrice(int n, vector<vector<int>> &edges, vector<int> &price,
                        vector<vector<int>> &trips) {
    vector<vector<int>> g(n);
    vector<int> cnt(n);
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      g[b].push_back(a);
    }
    function<bool(int, int, int)> dfs = [&](int i, int fa, int k) -> bool {
      ++cnt[i];
      if (i == k) {
        return true;
      }
      bool ok = false;
      for (int j : g[i]) {
        if (j != fa) {
          ok = dfs(j, i, k);
          if (ok) {
            break;
          }
        }
      }
      if (!ok) {
        --cnt[i];
      }
      return ok;
    };
    function<pair<int, int>(int, int)> dfs2 = [&](int i,
                                                  int fa) -> pair<int, int> {
      int a = cnt[i] * price[i];
      int b = a >> 1;
      for (int j : g[i]) {
        if (j != fa) {
          auto [x, y] = dfs2(j, i);
          a += min(x, y);
          b += x;
        }
      }
      return {a, b};
    };
    for (auto &t : trips) {
      int start = t[0], end = t[1];
      dfs(start, -1, end);
    }
    auto [a, b] = dfs2(0, -1);
    return min(a, b);
  }
};

```

### Python

```python
class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int: def dfs(i: int, fa: int, k: int) -> bool: cnt[i] += 1 if i == k: return True ok = any(j != fa and dfs(j, i, k) for j in g[i]) if not ok: cnt[i] -= 1 return ok def dfs2(i: int, fa: int) -> (int, int): a = cnt[i] * price[i] b = a // 2 for j in g[i]: if j != fa: x, y = dfs2(j, i) a += min(x, y) b += x return a, b g = [[] for _ in range(n)] for a, b in edges: g[a]. append(b) g[b]. append(a) cnt = Counter() for start, end in trips: dfs(start, - 1, end) return min(dfs2(0, - 1))

```