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

标签: 树 深度优先搜索 数组 动态规划

难度: Hard

给你一个 n 个节点的无向无根图，节点编号为 0 到 n - 1 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。

每个节点都有一个价值。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价值。

一条路径的 价值和 是这条路径上所有节点的价值之和。

你可以选择树中任意一个节点作为根节点 root 。选择 root 为根的 开销 是以 root 为起点的所有路径中，价值和 最大的一条路径与最小的一条路径的差值。

请你返回所有节点作为根节点的选择中，最大 的 开销 为多少。

示例 1：

输入：n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
输出：24
解释：上图展示了以节点 2 为根的树。左图（红色的节点）是最大价值和路径，右图（蓝色的节点）是最小价值和路径。
- 第一条路径节点为 [2,1,3,4]：价值为 [7,8,6,10] ，价值和为 31 。
- 第二条路径节点为 [2] ，价值为 [7] 。
最大路径和与最小路径和的差值为 24 。24 是所有方案中的最大开销。

示例 2：

输入：n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
输出：2
解释：上图展示了以节点 0 为根的树。左图（红色的节点）是最大价值和路径，右图（蓝色的节点）是最小价值和路径。
- 第一条路径包含节点 [0,1,2]：价值为 [1,1,1] ，价值和为 3 。
- 第二条路径节点为 [0] ，价值为 [1] 。
最大路径和与最小路径和的差值为 2 。2 是所有方案中的最大开销。

提示：

  • 1 <= n <= 105
  • edges.length == n - 1
  • 0 <= ai, bi <= n - 1
  • edges 表示一棵符合题面要求的树。
  • price.length == n
  • 1 <= price[i] <= 105

Submission

运行时间: 296 ms

内存: 49.1 MB

class Solution:
    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x) 

        res = 0
        def dfs(x, fa):
            nonlocal res 
            p = price[x]
            max_s1 = p
            max_s2 = 0
            for y in g[x]:
                if y == fa:
                    continue
                s1, s2 = dfs(y, x)
                res = max(res, max_s1 + s2, max_s2 + s1)
                max_s1 = max(max_s1, s1 + p)
                max_s2 = max(max_s2, s2 + p)
            return max_s1, max_s2
        

        dfs(0, -1)
        return res

Explain

此题解使用深度优先搜索（DFS）来计算以每个节点为根时的最大开销。首先，构建图的邻接表表示。然后，从任意节点（如节点0）开始进行DFS遍历。在遍历过程中，对于每一个节点x，计算以x为根节点的两种路径和：最大价值和（max_s1）和次大价值和（max_s2）。对于x的每一个孩子节点y，递归地计算以y为根的最大和次大路径和，并更新当前节点x的max_s1和max_s2。同时，在每次递归调用中，计算并更新全局最大开销res，确保记录下在所有可能的根选择中，最大路径和与最小路径和的最大差值。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        res = 0
        def dfs(x, fa):
            nonlocal res
            p = price[x]
            max_s1 = p
            max_s2 = 0
            for y in g[x]:
                if y == fa:
                    continue
                s1, s2 = dfs(y, x)
                res = max(res, max_s1 + s2, max_s2 + s1)
                max_s1 = max(max_s1, s1 + p)
                max_s2 = max(max_s2, s2 + p)
            return max_s1, max_s2

        dfs(0, -1)
        return res
        # g: 邻接表存储图
        # res: 记录最大的开销
        # dfs: 递归函数，计算以x为根节点的最大和次大路径和，同时更新最大开销res
        # p: 当前节点x的价值
        # max_s1: 以x为根的最大路径和
        # max_s2: 以x为根的次大路径和

Explore

在DFS过程中，每次从一个节点x向它的孩子节点y进行递归调用时，我们传递了当前节点x作为参数fa（父节点）。在节点y的DFS执行中，我们会检查每个邻接点是否为fa，如果是，就跳过这个邻接点，从而避免回到父节点x，这样就确保了每个节点的价值只被计算一次，避免了重复统计。同时，这种方法也确保了每个节点只与其子节点（而非父节点或已访问的兄弟节点）的路径和进行合并，确保了路径和的计算只在树的分支间进行，没有重复。

在DFS函数中，每个节点x计算得到两个值：max_s1（以x为根的最大路径和）和max_s2（以x为根的次大路径和）。对于x的每个孩子节点y，我们通过递归得到y的最大和次大路径和s1与s2。更新全局变量res的逻辑`res = max(res, max_s1 + s2, max_s2 + s1)`意味着我们不仅考虑了从当前节点x通过其某个孩子y回到x的两个最大可能路径和的组合（即x到y的最大路径和与其他孩子的次大路径和之和），还考虑了将这些路径和与其它可能的路径组合进行比较，从而更新全局最大的差值。这确保我们能够在所有可能的路径组合中找到最大的和差值。

是的，如果树极度不平衡，比如形成一个长链，DFS的递归调用栈可能非常深，从而引发栈溢出。为了解决这个问题，可以采用迭代的深度优先搜索（使用显式栈）或广度优先搜索（BFS）来代替递归的DFS。这样可以手动控制栈的使用，避免因递归过深而导致的栈溢出问题。另一种方法是使用尾递归优化，尽管这依赖于编程语言的编译器是否支持尾调用优化。