[HOT 100] 2538. 最大价值和与最小价值和的差值

1. 题目链接

2538. 最大价值和与最小价值和的差值 - 力扣（LeetCode）

2. 题目描述

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

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

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

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

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

3. 题目示例

示例 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 是所有方案中的最大开销。

4. 解题思路

1. 问题理解：
   • 给定一棵树和每个节点的价格
   • 需要找到两条路径，满足：
     • 第一条路径以叶子节点结束
     • 第二条路径不以叶子节点结束
   • 目标是最大化这两条路径和的差值
2. 关键思路：
   • 使用树形动态规划（Tree DP）方法
   • 对每个节点维护两个值：
     • maxS1: 包含叶子节点的最大路径和
     • maxS2: 不包含叶子节点的最大路径和
   • 通过DFS后序遍历计算这些值
3. 路径组合策略：
   • 对于每个节点，考虑将其作为两条路径的交汇点
   • 组合方式：
     • 左子树的maxS1 + 右子树的maxS2
     • 左子树的maxS2 + 右子树的maxS1
4. 初始化处理：
   • 叶子节点的maxS1初始化为节点价格
   • 叶子节点的maxS2初始化为0

5. 题解代码

class Solution {private List<Integer>[] g;  // 邻接表存储树结构private int[] price;        // 节点价格数组private long ans;           // 存储最终结果（最大输出差）public long maxOutput(int n, int[][] edges, int[] price) {this.price = price;// 初始化邻接表g = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());// 构建树结构for (var e : edges) {int x = e[0], y = e[1];g[x].add(y);g[y].add(x);}dfs(0, -1);  // 从根节点（假设为0）开始DFSreturn ans;}// DFS遍历树，返回两个值：// [0]: 以x为根的子树中，到叶子节点的最大路径和（包含叶子）// [1]: 以x为根的子树中，到非叶子节点的最大路径和（不包含叶子）private long[] dfs(int x, int fa) {long p = price[x];  // 当前节点价格long maxS1 = p;     // 包含叶子的最大路径和（初始化为当前节点价格）long maxS2 = 0;     // 不包含叶子的最大路径和（初始化为0）for (var y : g[x]) {if (y != fa) {  // 避免回溯父节点var res = dfs(y, x);  // 递归处理子节点long s1 = res[0], s2 = res[1];// 更新全局最大值ans：// 1. 前面最大带叶子的路径 + 当前不带叶子的路径// 2. 前面最大不带叶子的路径 + 当前带叶子的路径ans = Math.max(ans, Math.max(maxS1 + s2, maxS2 + s1));// 更新当前节点的两个最大值：// maxS1: 包含当前节点和子树的叶子路径// maxS2: 不包含子树叶子，但包含当前节点的路径maxS1 = Math.max(maxS1, s1 + p);maxS2 = Math.max(maxS2, s2 + p);}}return new long[]{maxS1, maxS2};}
}

6. 复杂度分析

时间复杂度：O(n)

• 每个节点仅被访问一次
• 每次访问执行常数时间操作
• n为树中节点数量

空间复杂度：O(n)

• 邻接表存储空间：O(n)
• 递归调用栈深度：最坏情况O(n)（树退化为链表）
• 其他辅助空间：O(1)