Leetcode 2646: Minimize the Total Price of the Trips

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:

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:

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

Problem Analysis:

Obviously it should use graph algorithm. we can use depth first search to find paths of every trips. Then we can compute total price sum of all trips.

But there is a condition: Before performing your first trip, you can choose some non-adjacent nodes and halve the prices.

Suppose we select the first node index is i, then for each adjacent nodes of node i, we can choose to halve its price or not. So we can know if we choose different first node, the total price sum may be different.

Fortunately, the count of nodes is small, n ≤ 50. we can try to iterate computing total price sum every time by choosing some node as the first node. Note the first node maybe halve its price or not. Finally we can get the minimum total sum is the answer.

Solution

class Solution {
public:
  int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
    vector<vector<int>> adj(n);
    vector<int> cost(n);
    vector<vector<int>> dp(n, vector<int>(2, -1));
    for (const auto& item : edges) {
      adj[item.front()].push_back(item.back());
      adj[item.back()].push_back(item.front());
    }
        
    for (const auto& item : trips) {
      vector<int> path;
      find(item.front(), path, cost, item.back(), adj, -1);
    }
    for (int i = 0; i < cost.size(); ++i) cost[i] *= price[i];
        
    return dfs(cost, 0, adj, dp, -1, 0);
  }

  void find(int node, vector<int>& path, vector<int>& cost, int end, vector<vector<int>>& adj, int p) {
    path.push_back(node);
    if (end == node) {
      for (const auto& item : path) ++cost[item];
      path.pop_back();
      return;
    }

    for (const auto& next : adj[node]) {
      if (next != p) find(next, path, cost, end, adj, node);
    }
    path.pop_back();
  }

  int dfs(vector<int>& cost, int node, vector<vector<int>>& adj, vector<vector<int>>& dp, int p = -1, bool p_half = false) {
    int half_cost = cost[node] / 2;
    int full_cost = cost[node];
    if (dp[node][p_half] != -1) return dp[node][p_half];

    for (const auto& next : adj[node]) {
      if (next != p) full_cost += dfs(cost, next, adj, dp, node, false);
    }
    if (p_half) return dp[node][p_half] = full_cost;
    
    for (const auto& next : adj[node]) {
      if (next != p) half_cost += dfs(cost, next, adj, dp, node, true);
    }
    return dp[node][p_half] = min(full_cost, half_cost);
  }
};

Time complexity is O(2^n)

Space complexity is O(n)