Welcome to Subscribe On Youtube
2538. Difference Between Maximum and Minimum Price Sum
Description
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:
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:
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 <= 105edges.length == n - 10 <= ai, bi <= n - 1edgesrepresents a valid tree.price.length == n1 <= price[i] <= 105
Solutions
Soution 1: Tree-shaped DP
Since the value of each node is a positive integer, the smallest path with node $root$ as the root node is the $root$ node itself. Therefore, the difference between the path with the maximum value sum and the smallest path is equivalent to removing one endpoint of the path.
We design a function $dfs(i, fa)$, which represents the maximum path sum in the subtree with node $i$ as the root node, with and without removing the endpoint. Here, $fa$ represents the parent node of node $i$.
The implementation logic of the function $dfs(i, fa)$ is as follows:
Initialize $a = price[i]$, $b = 0$, indicating that initially there is only one node, the maximum path sum without removing the endpoint is $price[i]$, and the maximum path sum with removing the endpoint is $0$.
For each child node $j$ of node $i$, if $j \ne fa$, then recursively call the function $dfs(j, i)$. Here, it returns the maximum path sum in the subtree with node $j$ as the root node, with and without removing the endpoint, denoted as $c$ and $d$. At this time, there are two cases for the answer:
- The maximum path sum without removing the endpoint plus the maximum path sum of the current node with removing the endpoint, that is, $a + d$;
- The maximum path sum with removing the endpoint plus the maximum path sum of the current node without removing the endpoint, that is, $b + c$.
We update the maximum value of the answer, that is, $ans = \max(ans, a + d, b + c)$.
Then update $a$ and $b$, that is, $a = \max(a, price[i] + c)$, $b = \max(b, price[i] + d)$, and finally return.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the number of nodes.
-
class Solution { private List<Integer>[] 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}; } } -
class Solution { public: long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) { vector<vector<int>> 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, ll>; ll ans = 0; function<pll(int, int)> 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; } }; -
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 -
func maxOutput(n int, edges [][]int, price []int) int64 { g := make([][]int, n) for _, e := range edges { a, b := e[0], e[1] g[a] = append(g[a], b) g[b] = append(g[b], a) } type pair struct{ a, b int } ans := 0 var dfs func(i, fa int) pair dfs = func(i, fa int) pair { a, b := price[i], 0 for _, j := range g[i] { if j != fa { e := dfs(j, i) c, d := e.a, e.b ans = max(ans, max(a+d, b+c)) a = max(a, price[i]+c) b = max(b, price[i]+d) } } return pair{a, b} } dfs(0, -1) return int64(ans) }