We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Difference Between Maximum and Minimum Price Sum

Number: 2627

Difficulty: Hard

Paid? No

Companies: Directi, Media.net

Problem Description

Given an undirected tree with n nodes (indexed 0 to n-1) and an array price where price[i] is the value at node i, we can “root” the tree at any node. For a chosen root, consider every simple path starting at the root. Each path’s "price sum" is the sum of prices for nodes on that path. The cost for that rooting is defined as the difference between the maximum and minimum price sum among these paths. (Note that the path that only contains the root has sum = price[root].) Our goal is to choose a root that maximizes this cost and return that maximum possible cost.

For example, in one test case the tree and prices are given by: n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]. When rooting the tree at node 2, one can obtain a maximum downward path [2,1,3,4] with sum 7+8+6+10 = 31. The trivial path just containing node 2 gives sum 7. Therefore cost = 31-7 = 24 (which turns out to be optimal).

Key Insights

  • When the tree is rooted at some node, every path starting from that root has at least the root’s price. Since all prices are positive, the trivial path (only the root) is the minimum price sum.
  • As a result, for a given root u, the cost is the maximum downward path sum (starting at u) minus price[u].
  • To efficiently evaluate the tree when “re‑rooting” at every node, we use a depth-first search (DFS) with re‑rooting techniques.
  • We compute two values for every node:
    • dp[u]: the maximum path sum in the subtree of u when the tree is rooted at an arbitrary start (thus considering only “downward” moves from u).
    • up[u]: the best value coming from above u (i.e. the contribution from the remainder of the tree if u were not the original DFS root).
  • Combining these, the maximum downward path sum when u is considered as root (i.e. freely choosing any neighbor) is f(u) = price[u] + max(0, up[u], (dp[u] - price[u])). Thus, the candidate cost if u is chosen as the root becomes f(u) - price[u] = max(0, up[u], dp[u] - price[u]).
  • The final answer is the maximum candidate cost over all nodes.

Space and Time Complexity

Time Complexity: O(n) – Each DFS traverses the tree linearly. Space Complexity: O(n) – Due to the recursion stack and auxiliary arrays (dp, up, best1, best2, and the adjacency list).

Solution

We use two DFS traversals:

  1. In the first DFS (from an arbitrary root, say node 0), compute dp[u] which is defined as: dp[u] = price[u] + max(0, maximum among {dp[v] for every child v of u}). During this DFS we also record for each node its best and second best dp values among its children. This information is needed to “exclude” a candidate when propagating upward.
  2. In the second DFS (re‑root phase), we compute for each child u of node p an up value: up[u] = price[p] + max( up[p], candidate ) where candidate is the best dp value among p’s children except u (if u provided the best dp at p, then we use the second best).
  3. For each node u, the maximum downward sum when choosing u as root is: f[u] = price[u] + max(0, up[u], dp_candidate) where dp_candidate is (dp[u] - price[u]). The cost if u is chosen as root is then f[u] - price[u] = max(0, up[u], dp[u] - price[u]).
  4. The answer is the maximum cost over all nodes.

We will now provide code solutions in Python, JavaScript, C++, and Java with detailed line‐by‐line comments.

Code Solutions

# Python solution
from collections import defaultdict, deque
import sys
sys.setrecursionlimit(10**6)

def maxPriceSumDifference(n, edges, price):
    # Build adjacency list for the undirected tree.
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # Arrays to store dp, up, best1, and best2 for each node.
    dp = [0] * n       # dp[u]: maximum downward path sum in the subtree of u.
    up = [0] * n       # up[u]: best contribution from parent's side when re-rooting.
    best1 = [-1] * n   # best1[u]: maximum dp value among children of u.
    best2 = [-1] * n   # best2[u]: second best dp value among children of u.
    
    # First DFS: compute dp[u] for each node (considering only subtree directions).
    def dfs1(u, parent):
        dp[u] = price[u]  # At minimum, the path just includes the node u.
        best1[u] = 0  # initialize best values as 0, as we allow skipping any branch.
        best2[u] = 0
        for v in graph[u]:
            if v == parent:
                continue
            dfs1(v, u)
            # If going to child v increases the sum, candidate = dp[v].
            candidate = dp[v]
            if candidate > best1[u]:
                best2[u] = best1[u]
                best1[u] = candidate
            elif candidate > best2[u]:
                best2[u] = candidate
        # If best branch gives a positive addition, add it.
        dp[u] += best1[u]
    
    dfs1(0, -1)
    
    # Second DFS: compute up[u] for all nodes (re-rooting technique)
    def dfs2(u, parent):
        for v in graph[u]:
            if v == parent:
                continue
            # Determine candidate from parent's children excluding v.
            candidate = best1[u]
            if dp[v] == best1[u]:
                candidate = best2[u]
            # up[v] gets parent's price combined with the better of parent's up or candidate.
            up[v] = price[u] + max(up[u], candidate)
            dfs2(v, u)
    
    up[0] = 0
    dfs2(0, -1)
    
    # Compute the answer: For each node u (if chosen as root), the maximum price sum is
    # f[u] = price[u] + max(0, up[u], (dp[u] - price[u])).
    # So the cost is f[u] - price[u] = max(0, up[u], dp[u] - price[u]).
    ans = 0
    for u in range(n):
        candidate_cost = max(0, up[u], dp[u] - price[u])
        ans = max(ans, candidate_cost)
    return ans

# Example usage:
n = 6
edges = [[0,1],[1,2],[1,3],[3,4],[3,5]]
price = [9,8,7,6,10,5]
print(maxPriceSumDifference(n, edges, price))  # Expected output: 24
← Back to All Questions