2538. 最大价值和与最小价值和的差值

2538. 最大价值和与最小价值和的差值

难度：Hard

提示：

1. 节点价值均为正数。
2. 最小价值和路径必定有且仅有一个节点。
3. 开销 = 最大价值和与最小价值和的差值，即去掉一个端点的路径价值和。
4. 最大开销即树中价值和最大的路径，此路径一定是从一个叶子节点到一个“前叶子节点”。
5. 树的路径和类问题，可以使用树形 DP 解决。
6. 树形 DP 的要点：
   1. 建图
   2. 最大路径和（或别的什么）依赖于父节点，父节点子树中的最大和次大路径和。
   3. 定义 dfs 函数，确定其返回值，即父节点遍历其每个子树时需要返回（依赖于）子树的哪些数值？
   4. 在遍历当前父节点的孩子节点的过程中找到最大和次大的和。并且更新以当前父节点为根的最大值与最终答案。
   5. 调用 dfs ，返回最终答案。

在本题中，关键的概念是开销，对于父节点，要计算包含父节点的开销，需要知道：子树中包含叶子节点的最大、次大路径和与不包含叶子节点的最大、次大路径和。对于最大和次大值，遍历一次邻接节点即可。在每次遍历后，要更新父节点子树中的最大路径和（包含与不包含叶子节点），还要更新最终答案。

class Solution:
    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:
        graph = [[] for _ in range(n)]
        for edge in edges:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
        ans = 0
        def dfs(cur: int, pre: int) -> int:
            nonlocal ans
            max_with_leaf = price[cur]
            max_no_leaf = 0
            for next in graph[cur]:
                if next == pre: continue
                with_leaf, no_leaf = dfs(next, cur)
                ans = max(ans, max_with_leaf + no_leaf, max_no_leaf + with_leaf)
                max_with_leaf = max(max_with_leaf, with_leaf + price[cur])
                max_no_leaf = max(max_no_leaf, no_leaf + price[cur])
            return max_with_leaf, max_no_leaf
        dfs(0, -1)
        return ans