What is the main pattern used in Difference Between Maximum and Minimum Price Sum?

The problem relies on binary-tree traversal and state tracking to calculate path sums efficiently.

How do I find the minimum path sum?

The minimum path sum is always the price of a single node, typically chosen as the root or any leaf.

Can this solution handle large n values?

Yes, using DFS with state tracking ensures O(n) time and space complexity, suitable for up to 10^5 nodes.

Do I need dynamic programming for this problem?

Yes, dynamic programming on tree edges allows tracking maximum path sums without redundant computations.

How is the final difference calculated?

Subtract the minimum single-node price from the maximum path sum recorded during DFS traversal to get the answer.

#2538

Hard

auto_awesome二分·树·traversal

LeetCode 题解工作台

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

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

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

题目描述

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

每个节点都有一个价值。给你一个整数数组 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 <= 10⁵
edges.length == n - 1
0 <= a_i, b_i <= n - 1
edges 表示一棵符合题面要求的树。
price.length == n
1 <= price[i] <= 10⁵

lightbulb

解题思路

方法一：树形 DP

由于每个节点价值均为正整数，因此，以节点 $root$ 作为根节点的最小的一条路径就是 $root$ 节点本身，那么价值和最大的一条路径与最小的一条路径的差值就等价于去掉路径的一个端点。

我们设计一个函数 $dfs(i, fa)$ ，表示以节点 $i$ 为根节点的子树中，不去掉端点的最大路径和以及去掉端点的最大路径和。其中， $fa$ 表示节点 $i$ 的父节点。

函数 $dfs(i, fa)$ 的实现逻辑如下：

初始化 $a = price[i]$ , $b = 0$ ，表示初始只有一个节点，不去掉端点的最大路径和为 $price[i]$ ，去掉端点的最大路径和为 $0$ 。

对于节点 $i$ 的每个子节点 $j$ ，如果 $j \ne fa$ ，则递归调用函数 $dfs(j, i)$ ，这里返回了以节点 $j$ 为根节点的子树中，不去掉端点的最大路径和以及去掉端点的最大路径和，记为 $c$ 和 $d$ 。此时答案有两种情况：

前面不去掉端点的最大路径和加上当前节点去掉端点的最大路径和，即 $a + d$ ；
前面去掉端点的最大路径和加上当前节点不去掉端点的最大路径和，即 $b + c$ 。

我们更新答案的最大值，即 $ans = \max(ans, a + d, b + c)$ 。

然后更新 $a$ 和 $b$ ，即 $a = \max(a, price[i] + c)$ , $b = \max(b, price[i] + d)$ ，最后返回。

时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。其中 $n$ 为节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

speed

复杂度分析

指标	值
时间	complexity is O(n) due to a single DFS traversal through all nodes. Space complexity is O(n) for storing subtree states and recursion stack, which scales with the tree size.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect efficient handling of trees with up to 10^5 nodes, highlighting binary-tree traversal mastery.
question_mark
Demonstrate understanding of state tracking and dynamic programming across tree edges.
question_mark
Recognize that the minimum price sum is always a single node, which guides optimal traversal.

warning

常见陷阱

外企场景

error
Forgetting to consider single-node paths as minimum sum, leading to incorrect difference.
error
Recomputing path sums for overlapping subtrees instead of tracking state, causing inefficiency.
error
Incorrectly summing path prices without maintaining subtree maximums, missing the global maximum difference.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute difference between maximum and minimum weighted path sums with additional edge costs.
arrow_right_alt
Extend the problem to handle multiple disconnected trees (forest) and report maximum differences per tree.
arrow_right_alt
Modify node prices dynamically and recalculate the maximum difference efficiently for online queries.

help

常见问题

外企场景

继续练习

#2581 统计可能的树根数目 #2646 最小化旅行的价格总和 #2920 收集所有金币可获得的最大积分