Difference Between Maximum and Minimum Price Sum — LeetCode 2538 Python Solution

The problem

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.

Example

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.

Python solution

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

Complexity

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 2538. Difference Between Maximum and Minimum Price Sum is filed here because LeetCode tags it Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems