LeetCode 2646: Minimize the Total Price of the Trips Solution

Master LeetCode problem 2646 (Minimize the Total Price of the Trips), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2646. Minimize the Total Price of the Trips

Hard

Array Dynamic Programming Tree Depth-First Search Graph

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming on trees. We can start from any node as the root of the tree and traverse the tree in a bottom-up manner. At each node, we need to consider two cases:

Whether to keep the current node's price as it is.
Whether to halve the current node's price and propagate that change to its children.

We can maintain a 3D dp array to store the minimum total price for each node, the number of nodes that have their price halved, and the last node where the price was halved. By considering these two cases at each node, we can calculate the minimum total price for all trips.

Time Complexity:

The time complexity of this solution is O(n) where n is the number of nodes in the tree.

Space Complexity:

The space complexity of this solution is O(n) for the dp array.

Solution Code

class Solution {
    public int minCost(int n, int[][] edges, int[] price, int[][] trips) {
        List<List<Integer>> tree = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            tree.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            tree.get(edge[0]).add(edge[1]);
            tree.get(edge[1]).add(edge[0]);
        }
        int[][][] dp = new int[n][n][2];
        dfs(0, -1, tree, price, dp);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.min(res, dp[i][0][0]);
        }
        return res;
    }
    
    private void dfs(int node, int parent, List<List<Integer>> tree, int[] price, int[][][] dp) {
        dp[node][0][0] = price[node];
        dp[node][0][1] = 0;
        for (int child : tree.get(node)) {
            if (child == parent) continue;
            dfs(child, node, tree, price, dp);
            int[][] temp = new int[dp[node].length][2];
            for (int i = 0; i < dp[node].length; i++) {
                for (int j = 0; j <= dp[node][i][1]; j++) {
                    for (int k = 0; k < dp[child].length; k++) {
                        int cnt = i + k + 1;
                        int newPrice = dp[node][i][0] + dp[child][k][0];
                        if (j == 0) {
                            temp[cnt][0] = Math.min(temp[cnt][0], newPrice);
                        } else {
                            temp[cnt][0] = Math.min(temp[cnt][0], (int) Math.ceil(newPrice / 2.0));
                        }
                        temp[cnt][1] = Math.max(temp[cnt][1], j);
                    }
                }
            }
            dp[node] = temp;
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2646 (Minimize the Total Price of the Trips)?

This page provides optimized solutions for LeetCode problem 2646 (Minimize the Total Price of the Trips) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2646 (Minimize the Total Price of the Trips)?

The time complexity for LeetCode 2646 (Minimize the Total Price of the Trips) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2646 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2646 in Java, C++, or Python.

Back to LeetCode Solutions