Difference Between Maximum and Minimum Price Sum
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 i^th 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
Input
n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]Output
24Rooting the tree at node 2 gives a maximum price-sum path
[2, 1, 3, 4] with sum 31 and a minimum path [2] with sum 7, so the maximum possible cost is 24.Example 2
Input
n = 3, edges = [[0,1],[1,2]], price = [1,1,1]Output
2Rooting the tree at node 0 gives a maximum price-sum path
[0, 1, 2] with sum 3 and a minimum path [0] with sum 1, so the maximum possible cost is 2.Constraints
- 1 <= n <= 10^5
- edges.length == n - 1
- 0 <= ai, bi <= n - 1
- edges represents a valid tree.
- price.length == n
- 1 <= price[i] <= 10^5