这道题是LeetCode 2538核心思路是树形DP通过一次DFS遍历同时维护两个状态来求解最大差值。问题分析给定一棵树每个节点有 price[i]。我们可以选择任意节点作为根 root定义“开销”为以 root 为起点的所有路径中最大路径和与最小路径和的差值。由于所有节点价值均为正数最小路径和一定是只包含根节点自身即路径长度为1所以问题转化为对于每个节点作为根求从它出发到某个叶子节点的最大路径和减去它自身的价值取所有节点中的最大值。进一步等价于求树中一条路径两端都是叶子节点的总和减去其中一个叶子节点的价值得到的最大值。核心思路树形DPDFS返回两个值- maxS1从当前节点出发包含叶子节点的最大路径和即路径终点是叶子- maxS2从当前节点出发不包含叶子节点的最大路径和即路径终点是非叶子节点对于每个节点遍历其子节点时用已遍历的最大值与当前子节点的值组合更新全局答案ans max(ans, maxS1 child.maxS2, maxS2 child.maxS1)然后更新当前节点的两个状态maxS1 max(maxS1, child.maxS1 price[cur])maxS2 max(maxS2, child.maxS2 price[cur])Java实现class Solution {private ListInteger[] 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 (int[] e : edges) {int x e[0], y e[1];g[x].add(y);g[y].add(x);}dfs(0, -1);return ans;}// 返回 [包含叶子的最大路径和, 不包含叶子的最大路径和]private long[] dfs(int x, int fa) {long p price[x];long maxS1 p; // 包含叶子初始化为自身long maxS2 0; // 不包含叶子初始化为0叶子节点本身不算for (int y : g[x]) {if (y fa) continue;long[] child dfs(y, x);long s1 child[0], s2 child[1];// 用当前节点作为两条路径的交汇点组合更新答案ans Math.max(ans, Math.max(maxS1 s2, maxS2 s1));// 更新当前节点的两个状态maxS1 Math.max(maxS1, s1 p);maxS2 Math.max(maxS2, s2 p);}return new long[]{maxS1, maxS2};}}复杂度分析- 时间复杂度O(n)每个节点只遍历一次- 空间复杂度O(n)邻接表和递归栈空间示例验证示例1n 6, edges [[0,1],[1,2],[1,3],[3,4],[3,5]], price [9,8,7,6,10,5]输出24路径 [2,1,3,4] 价值和为 31减去叶子节点 2 的价值 7得 24。示例2n 3, edges [[0,1],[1,2]], price [1,1,1]输出2路径 [0,1,2] 价值和为 3减去叶子节点 0 的价值 1得 2。关键点总结1. 由于所有价值为正最小路径就是根节点自身所以问题简化为最大路径和减去一个端点价值2. 用树形DP维护包含叶子和不包含叶子两种路径的最大和3. 在遍历子节点时用已遍历部分与当前子节点组合更新答案避免重复计算