Skip to content

2538. Difference Between Maximum and Minimum Price Sum 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
 public:
  long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) {
    int ans = 0;
    vector<vector<int>> graph(n);
    vector<int> maxSums(n);  // maxSums[i] := max sum of path rooted at i.

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    // Precalculate `maxSums`.
    maxSum(graph, 0, /*prev=*/-1, maxSums, price);
    reroot(graph, 0, /*prev=*/-1, /*parentSum=*/0, maxSums, price, ans);
    return ans;
  }

 private:
  int maxSum(const vector<vector<int>>& graph, int u, int prev,
             vector<int>& maxSums, const vector<int>& price) {
    int maxChildSum = 0;
    for (const int v : graph[u])
      if (prev != v)
        maxChildSum = max(maxChildSum, maxSum(graph, v, u, maxSums, price));
    return maxSums[u] = price[u] + maxChildSum;
  }

  void reroot(const vector<vector<int>>& graph, int u, int prev, int parentSum,
              const vector<int>& maxSums, const vector<int>& price, int& ans) {
    // Get top two subtree sums and top one node index.
    int maxSubtreeSum1 = 0;
    int maxSubtreeSum2 = 0;
    int maxNode = -1;
    for (const int v : graph[u]) {
      if (v == prev)
        continue;
      if (maxSums[v] > maxSubtreeSum1) {
        maxSubtreeSum2 = maxSubtreeSum1;
        maxSubtreeSum1 = maxSums[v];
        maxNode = v;
      } else if (maxSums[v] > maxSubtreeSum2) {
        maxSubtreeSum2 = maxSums[v];
      }
    }

    if (graph[u].size() == 1)
      ans = max({ans, parentSum, maxSubtreeSum1});

    for (const int v : graph[u]) {
      if (v == prev)
        continue;
      const int nextParentSum =
          (v == maxNode ? price[u] + max(parentSum, maxSubtreeSum2)
                        : price[u] + max(parentSum, maxSubtreeSum1));
      reroot(graph, v, u, nextParentSum, maxSums, price, ans);
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
  public long maxOutput(int n, int[][] edges, int[] price) {
    List<Integer>[] graph = new List[n];
    int[] maxSums = new int[n]; // maxSums[i] := max sum of path rooted at i.

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      graph[u].add(v);
      graph[v].add(u);
    }

    // Precalculate `maxSums`.
    maxSum(graph, 0, /*prev=*/-1, maxSums, price);
    reroot(graph, 0, /*prev=*/-1, /*parentSum=*/0, maxSums, price);
    return (long) ans;
  }

  private int ans = 0;

  private int maxSum(List<Integer>[] graph, int u, int prev, int[] maxSums, int[] price) {
    int maxChildSum = 0;
    for (final int v : graph[u])
      if (prev != v)
        maxChildSum = Math.max(maxChildSum, maxSum(graph, v, u, maxSums, price));
    return maxSums[u] = price[u] + maxChildSum;
  }

  private void reroot(List<Integer>[] graph, int u, int prev, int parentSum, int[] maxSums,
                      int[] price) {
    // Get top two sums and top one node index.
    int maxSubtreeSum1 = 0;
    int maxSubtreeSum2 = 0;
    int maxNode = -1;
    for (final int v : graph[u]) {
      if (v == prev)
        continue;
      if (maxSums[v] > maxSubtreeSum1) {
        maxSubtreeSum2 = maxSubtreeSum1;
        maxSubtreeSum1 = maxSums[v];
        maxNode = v;
      } else if (maxSums[v] > maxSubtreeSum2) {
        maxSubtreeSum2 = maxSums[v];
      }
    }

    if (graph[u].size() == 1)
      ans = Math.max(ans, Math.max(parentSum, maxSubtreeSum1));

    for (final int v : graph[u]) {
      if (v == prev)
        continue;
      final int nextParentSum = (v == maxNode ? price[u] + Math.max(parentSum, maxSubtreeSum2)
                                              : price[u] + Math.max(parentSum, maxSubtreeSum1));
      reroot(graph, v, u, nextParentSum, maxSums, price);
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution:
  def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:
    ans = 0
    graph = [[] for _ in range(n)]
    maxSums = [0] * n  # maxSums[i] := max sum of path rooted at i.

    for u, v in edges:
      graph[u].append(v)
      graph[v].append(u)

    def maxSum(u: int, prev: int) -> int:
      maxChildSum = 0
      for v in graph[u]:
        if prev != v:
          maxChildSum = max(maxChildSum, maxSum(v, u))
      maxSums[u] = price[u] + maxChildSum
      return maxSums[u]

    # Precalculate `maxSums`.
    maxSum(0, -1)

    def reroot(u: int, prev: int, parentSum: int) -> None:
      nonlocal ans
      # Get top two subtree sums and top one node index.
      maxSubtreeSum1 = 0
      maxSubtreeSum2 = 0
      maxNode = -1
      for v in graph[u]:
        if v == prev:
          continue
        if maxSums[v] > maxSubtreeSum1:
          maxSubtreeSum2 = maxSubtreeSum1
          maxSubtreeSum1 = maxSums[v]
          maxNode = v
        elif maxSums[v] > maxSubtreeSum2:
          maxSubtreeSum2 = maxSums[v]

      if len(graph[u]) == 1:
        ans = max(ans, parentSum, maxSubtreeSum1)

      for v in graph[u]:
        if v == prev:
          continue
        nextParentSum = \
            price[u] + max(parentSum, maxSubtreeSum2) if v == maxNode else \
            price[u] + max(parentSum, maxSubtreeSum1)
        reroot(v, u, nextParentSum)

    reroot(0, -1, 0)
    return ans