Difference Between Maximum and Minimum Price Sum
01 · Problem
You are given an undirected tree with n nodes labelled 0 to n - 1, where edges[i] = [a_i, b_i] connects a_i and b_i, and an array price where price[i] is the (positive) price of node i.
The price sum of a path is the sum of the prices of all nodes on it. You may choose any node as the root. For a chosen root, consider every path that starts at the root and goes downward (a path consisting of the root alone is allowed). The cost of that rooting is the maximum price sum among those paths minus the minimum price sum among them.
Since prices are positive, the minimum path is always the root alone. Return the largest cost over all possible choices of root.
02 · Examples
n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
24
Root the tree at node 2. The most expensive path from it is 2 -> 1 -> 3 -> 4 with sum 7 + 8 + 6 + 10 = 31, and the cheapest is node 2 alone with sum 7, giving 31 - 7 = 24.
n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
2
Rooting at node 0, the longest path 0 -> 1 -> 2 costs 3 and the cheapest path (just node 0) costs 1, so the cost is 2.
n = 1, edges = [], price = [5]
0
With a single node, the only path from the root is the root itself, so the difference is 0.
03 · Constraints
- 011 <= n <= 105
- 02edges.length == n - 1 and the edges form a valid tree.
- 030 <= a_i, b_i < n and a_i != b_i
- 04price.length == n
- 051 <= price[i] <= 105
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.