# Difference Between Maximum and Minimum Price Sum **Difficulty:** HARD [External](https://leetcode.com/problems/difference-between-maximum-and-minimum-price-sum) Canonical: https://scaleengineer.com/dsa/problems/difference-between-maximum-and-minimum-price-sum **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 **Companies:** [Media.net](https://scaleengineer.com/companies/media.net), [Directi](https://scaleengineer.com/companies/directi) --- ## Problem There exists an undirected and initially 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. The tree can be rooted at any node `root` of your choice. The incurred **cost** after choosing `root` is the difference between the maximum and minimum **price sum** amongst all paths starting at `root`. Return _the **maximum** possible **cost**_ _amongst all possible root choices_. **Example 1:** ![](https://assets.glich.co/dsa/difference-between-maximum-and-minimum-price-sum/image0.png) **Input:** n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5] **Output:** 24 **Explanation:** The diagram above denotes the tree after rooting it at node 2. The first part (colored in red) shows the path with the maximum price sum. The second part (colored in blue) shows the path with the minimum price sum. - The first path contains nodes [2,1,3,4]: the prices are [7,8,6,10], and the sum of the prices is 31. - The second path contains the node [2] with the price [7]. The difference between the maximum and minimum price sum is 24. It can be proved that 24 is the maximum cost. **Example 2:** ![](https://assets.glich.co/dsa/difference-between-maximum-and-minimum-price-sum/image1.png) **Input:** n = 3, edges = [[0,1],[1,2]], price = [1,1,1] **Output:** 2 **Explanation:** The diagram above denotes the tree after rooting it at node 0. The first part (colored in red) shows the path with the maximum price sum. The second part (colored in blue) shows the path with the minimum price sum. - The first path contains nodes [0,1,2]: the prices are [1,1,1], and the sum of the prices is 3. - The second path contains node [0] with a price [1]. The difference between the maximum and minimum price sum is 2. It can be proved that 2 is the maximum cost. **Constraints:** * `1 <= n <= 105` * `edges.length == n - 1` * `0 <= ai, bi <= n - 1` * `edges` represents a valid tree. * `price.length == n` * `1 <= price[i] <= 105` # Approaches ## Brute Force by Iterating Through All Possible Roots The most straightforward approach is to simulate the process described in the problem. We can iterate through every node, consider it as the root, calculate the cost associated with it, and find the maximum cost among all possible roots. **Time:** O(N^2), where N is the number of nodes. For each of the N possible roots, we perform a graph traversal (BFS/DFS) which takes O(N + E) time. Since it's a tree, E = N-1, so each traversal is O(N). The total time complexity is N * O(N) = O(N^2). · **Space:** O(N), where N is the number of nodes. We need O(N) space for the adjacency list. Additionally, during each traversal, we use a queue or recursion stack and a visited array, which take O(N) space. **Pros:** Simple to understand and implement directly from the problem definition. **Cons:** Inefficient for large inputs. An O(N^2) solution will likely result in a 'Time Limit Exceeded' error for constraints where N is up to 10^5. ### Explanation For each node `i` from `0` to `n-1`, we treat it as the root of the tree. The cost for a given root is the difference between the maximum and minimum price sum of all paths starting from that root. The minimum price sum for any path starting at root `i` is simply the price of the node `i` itself, `price[i]`, as this corresponds to the path containing only the root. To find the maximum price sum, we need to find the path starting at `i` that yields the highest sum of prices. This can be achieved by performing a graph traversal, like Breadth-First Search (BFS) or Depth-First Search (DFS), starting from node `i`. During the traversal, we keep track of the cumulative price sum for each path from `i`. After the traversal completes, we will have found the maximum path sum starting from `i`. The cost for root `i` is then `max_path_sum - price[i]`. We repeat this process for all `n` nodes and return the maximum cost found. Here is a Java implementation using this approach:\n```java\nclass Solution {\n public long maxOutput(int n, int[][] edges, int[] price) {\n List> adj = new ArrayList<>();\n for (int i = 0; i < n; i++) {\n adj.add(new ArrayList<>());\n }\n for (int[] edge : edges) {\n adj.get(edge[0]).add(edge[1]);\n adj.get(edge[1]).add(edge[0]);\n }\n\n long maxOverallCost = 0;\n\n for (int i = 0; i < n; i++) {\n long maxPathSumFromI = 0;\n Queue queue = new LinkedList<>();\n queue.offer(new long[]{i, price[i]}); // {node, current_path_sum}\n boolean[] visited = new boolean[n];\n visited[i] = true;\n\n while (!queue.isEmpty()) {\n long[] current = queue.poll();\n int u = (int) current[0];\n long currentSum = current[1];\n maxPathSumFromI = Math.max(maxPathSumFromI, currentSum);\n\n for (int v : adj.get(u)) {\n if (!visited[v]) {\n visited[v] = true;\n queue.offer(new long[]{v, currentSum + price[v]});\n }\n }\n }\n \n long costI = maxPathSumFromI - price[i];\n maxOverallCost = Math.max(maxOverallCost, costI);\n }\n\n return maxOverallCost;\n }\n}\n``` ### Algorithm - Build an adjacency list representation of the tree from the `edges` array.\n- Initialize a variable `max_cost` to 0.\n- Iterate through each node `i` from `0` to `n-1`, considering it as the potential root.\n- For each `i`, perform a graph traversal (like BFS) starting from `i` to find the maximum price sum of a path starting at `i`.\n- In the traversal, maintain the sum of prices along the current path. Keep track of the maximum sum found.\n- After the traversal, calculate the cost for root `i` as `max_path_sum_from_i - price[i]`.\n- Update `max_cost = max(max_cost, cost_for_i)`.\n- After iterating through all nodes, `max_cost` will hold the result. ## Optimal Approach using Tree Price Diameter A much more efficient approach relies on a key insight about tree paths. The cost for any root `i` depends on the maximum price sum path starting from `i`. It turns out this path always ends at one of the two endpoints of a 'price diameter' of the tree. A 'price diameter' is a path between two nodes with the maximum possible sum of prices. By pre-calculating information related to the diameter, we can find the answer in linear time. **Time:** O(N), where N is the number of nodes. The algorithm consists of three separate graph traversals (BFS/DFS), each taking O(N) time. The final loop to calculate the maximum cost also takes O(N). Thus, the total time complexity is linear. · **Space:** O(N), where N is the number of nodes. This space is used for the adjacency list, the distance arrays (`dist_x`, `dist_y`), and the data structures required for traversal (queue for BFS or recursion stack for DFS). **Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; It's an optimal solution for this problem. **Cons:** The solution is not immediately obvious and relies on understanding a specific property of trees (the diameter concept), making it more complex to derive than the brute-force approach. ### Explanation The core idea is to transform the problem from re-calculating path sums for each root to a problem that can be solved with a few global traversals.\n1. **Price Diameter**: First, we define a 'price diameter' as a path between two nodes `u` and `v` such that the sum of prices of all nodes on the path is maximized over the entire tree.\n2. **Key Insight**: For any node `i` in the tree, the path starting at `i` with the maximum price sum will always end at one of the endpoints of any price diameter. Let's say the endpoints of a price diameter are `x` and `y`. Then, for any `i`, the maximum price sum path starting from `i` is `max(S(i, x), S(i, y))`, where `S(u, v)` is the price sum of the path between `u` and `v`. The minimum price sum path is always `price[i]`. Therefore, the cost for root `i` is `cost(i) = max(S(i, x), S(i, y)) - price[i]`.\n3. **Algorithm**: The problem is now reduced to: find diameter endpoints `x` and `y`, then for every node `i`, find its path sum to `x` and `y`, and compute the maximum cost. This can be done efficiently.\nHere is the Java implementation:\n```java\nimport java.util.*;\n\nclass Solution {\n private List> adj;\n private int[] price;\n private int n;\n\n public long maxOutput(int n, int[][] edges, int[] price) {\n this.n = n;\n this.price = price;\n this.adj = new ArrayList<>();\n for (int i = 0; i < n; i++) {\n adj.add(new ArrayList<>());\n }\n for (int[] edge : edges) {\n adj.get(edge[0]).add(edge[1]);\n adj.get(edge[1]).add(edge[0]);\n }\n\n // Step 1: Find endpoints of a price diameter (x, y)\n Object[] res1 = bfs(0);\n int x = (int) res1[0];\n\n Object[] res2 = bfs(x);\n int y = (int) res2[0];\n long[] distFromX = (long[]) res2[2];\n\n // Step 2: Get distances from y\n Object[] res3 = bfs(y);\n long[] distFromY = (long[]) res3[2];\n\n // Step 3: Calculate max cost\n long maxCost = 0;\n for (int i = 0; i < n; i++) {\n long cost = Math.max(distFromX[i], distFromY[i]) - price[i];\n maxCost = Math.max(maxCost, cost);\n }\n\n return maxCost;\n }\n\n private Object[] bfs(int startNode) {\n long[] dist = new long[n];\n Arrays.fill(dist, -1);\n Queue queue = new LinkedList<>();\n\n queue.offer(startNode);\n dist[startNode] = price[startNode];\n\n int farthestNode = startNode;\n long maxDist = price[startNode];\n\n while (!queue.isEmpty()) {\n int u = queue.poll();\n for (int v : adj.get(u)) {\n if (dist[v] == -1) { // Not visited\n dist[v] = dist[u] + price[v];\n if (dist[v] > maxDist) {\n maxDist = dist[v];\n farthestNode = v;\n }\n queue.offer(v);\n }\n }\n }\n return new Object[]{farthestNode, maxDist, dist};\n }\n}\n``` ### Algorithm - **Step 1: Find endpoints of a price diameter (`x`, `y`).** This is a standard two-pass traversal algorithm.\n - a. Pick an arbitrary node (e.g., 0). Run a BFS/DFS to find the node `x` farthest from it in terms of price sum.\n - b. Run a BFS/DFS from `x` to find the node `y` farthest from `x`. The path between `x` and `y` is a price diameter.\n- **Step 2: Calculate path sums from `x` and `y` to all other nodes.**\n - The traversal from `x` in Step 1b already gives us the path sums from `x` to all other nodes (`S(x, i)`). Store these in an array `dist_x`.\n - Run one more BFS/DFS, this time starting from `y`, to compute `S(y, i)` for all `i`. Store these in an array `dist_y`.\n- **Step 3: Calculate the maximum cost.**\n - Initialize `max_cost = 0`.\n - Iterate `i` from `0` to `n-1`:\n - `cost_i = max(dist_x[i], dist_y[i]) - price[i]`.\n - `max_cost = max(max_cost, cost_i)`.\n - Return `max_cost`. # Solutions ### Java ```java class Solution { private List[] g; private long ans; private int[] price; public long maxOutput(int n, int[][] edges, int[] price) { 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); } this.price = price; dfs(0, -1); return ans; } private long[] dfs(int i, int fa) { long a = price[i], b = 0; for (int j : g[i]) { if (j != fa) { var e = dfs(j, i); long c = e[0], d = e[1]; ans = Math.max(ans, Math.max(a + d, b + c)); a = Math.max(a, price[i] + c); b = Math.max(b, price[i] + d); } } return new long[]{a, b}; } } ``` ### CPP ```cpp class Solution { public: long long maxOutput(int n, vector> &edges, vector &price) { vector> g(n); for (auto &e : edges) { int a = e[0], b = e[1]; g[a].push_back(b); g[b].push_back(a); } using ll = long long; using pll = pair; ll ans = 0; function dfs = [&](int i, int fa) { ll a = price[i], b = 0; for (int j : g[i]) { if (j != fa) { auto [c, d] = dfs(j, i); ans = max({ans, a + d, b + c}); a = max(a, price[i] + c); b = max(b, price[i] + d); } } return pll{a, b}; }; dfs(0, -1); return ans; } }; ``` ### Python ```python class Solution: def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int: def dfs(i, fa): a, b = price[i], 0 for j in g[i]: if j != fa: c, d = dfs(j, i) nonlocal ans ans = max(ans, a + d, b + c) a = max(a, price[i] + c) b = max(b, price[i] + d) return a, b g = defaultdict(list) for a, b in edges: g[a]. append(b) g[b]. append(a) ans = 0 dfs(0, - 1) return ans ```