867. Price Spread in a Tree
A trade network has n towns numbered 0 to n - 1, joined by n - 1 roads (edges[i] = [a, b]) so that exactly one route exists between any two towns. Visiting town i adds price[i] to the cost of a journey; prices can be negative (subsidies).
Pick a starting town r and consider every journey that begins at r and follows the unique route to some town, including the journey that never leaves r. The cost of a journey is the sum of the prices of all towns on its route, both ends included. The spread of r is the largest journey cost minus the smallest journey cost among those journeys. Return the maximum spread over all possible starting towns.
Example 1
- Input:
- n = 4, edges = [[0,1],[1,2],[1,3]], price = [3,2,5,-4]
- Output:
- 9
- Explanation:
Starting at town 0 the journeys cost 3, 5, 10 and 1, spread 9; starting at town 1 they cost 2, 5, 7 and -2, also spread 9; towns 2 and 3 give spread 7. The maximum is 9.
Example 2
- Input:
- n = 3, edges = [[0,1],[1,2]], price = [1,-5,4]
- Output:
- 5
- Explanation:
From town 0 the journey costs are 1, -4 and 0 (spread 5); from town 1 they are -5, -4 and -1 (spread 4); from town 2 they are 4, -1 and 0 (spread 5). The maximum is 5.
Constraints
- 1 ≤ n ≤ 105
edges.length == n - 1, 0 ≤ a, b < n and the roads form a tree- -109 ≤ price[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)