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 <= 10^5
  • edges.length == n - 1
  • 0 <= ai, bi <= n - 1
  • edges 表示一棵有效的树
  • price.length == n
  • 1 <= price[i] <= 10^5

解题思路

这道题要求找到最大的代价（从根节点出发的所有路径中，最大价格和与最小价格和的差值）。

核心观察：

  1. 最小价格和总是根节点的价格（单个节点的路径）
  2. 最大价格和是从根节点到某个叶子节点的路径
  3. 因此问题转化为：对于每个可能的根节点，找到从该根节点到叶子节点的最大路径和

解题思路： 使用两次DFS的换根DP方法：

  1. 第一次DFS（自底向上）： 以任意节点（如节点0）为根，计算每个节点向下的最大路径和。对于每个节点，我们需要知道：

    • down[u]：从节点u向下到叶子的最大价格和

  2. 第二次DFS（自顶向下）： 利用换根技巧，计算每个节点作为根时的答案。对于每个节点，我们需要知道：

    • up[u]：从节点u向上（通过父节点）能达到的最大价格和

  3. 状态转移：

    • down[u] = price[u] + max(down[v]) 其中v是u的子节点
    • up[u] = max(price[parent] + up[parent], price[parent] + max_other_down) 其中max_other_down是父节点除u外其他子树的最大down值

  4. 答案计算： 对于每个节点u作为根，答案是 max(down[u], up[u]) - price[u]

优化细节：

  • 需要维护每个节点的最大和次大down值，用于换根时的计算
  • 使用long long避免溢出

代码实现

class Solution {
public:
    long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) {
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        vector<long long> down(n, 0);
        vector<long long> up(n, 0);
        
        function<void(int, int)> dfs1 = [&](int u, int parent) {
            down[u] = price[u];
            for (int v : graph[u]) {
                if (v != parent) {
                    dfs1(v, u);
                    down[u] = max(down[u], price[u] + down[v]);
                }
            }
        };
        
        function<void(int, int)> dfs2 = [&](int u, int parent) {
            vector<long long> childValues;
            for (int v : graph[u]) {
                if (v != parent) {
                    childValues.push_back(down[v]);
                }
            }
            
            if (parent != -1) {
                childValues.push_back(up[u]);
            }
            
            sort(childValues.rbegin(), childValues.rend());
            
            for (int v : graph[u]) {
                if (v != parent) {
                    up[v] = price[u];
                    if (childValues.size() >= 2) {
                        if (down[v] == childValues[0]) {
                            up[v] = max(up[v], price[u] + childValues[1]);
                        } else {
                            up[v] = max(up[v], price[u] + childValues[0]);
                        }
                    } else if (childValues.size() == 1 && down[v] != childValues[0]) {
                        up[v] = max(up[v], price[u] + childValues[0]);
                    }
                    dfs2(v, u);
                }
            }
        };
        
        dfs1(0, -1);
        dfs2(0, -1);
        
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            ans = max(ans, max(down[i], up[i]) - price[i]);
        }
        
        return ans;
    }
};

class Solution:
    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        down = [0] * n
        up = [0] * n
        
        def dfs1(u, parent):
            down[u] = price[u]
            for v in graph[u]:
                if v != parent:
                    dfs1(v, u)
                    down[u] = max(down[u], price[u] + down[v])
        
        def dfs2(u, parent):
            child_values = []
            for v in graph[u]:
                if v != parent:
                    child_values.append(down[v])
            
            if parent != -1:
                child_values.append(up[u])
            
            child_values.sort(reverse=True)
            
            for v in graph[u]:
                if v != parent:
                    up[v] = price[u]
                    if len(child_values) >= 2:
                        if down[v] == child_values[0]:
                            up[v] = max(up[v], price[u] + child_values[1])
                        else:
                            up[v] = max(up[v], price[u] + child_values[0])
                    elif len(child_values) == 1 and down[v] != child_values[0]:
                        up[v] = max(up[v], price[u] + child_values[0])
                    dfs2(v, u)
        
        dfs1(0, -1)
        dfs2(0, -1)
        
        ans = 0
        for i in range(n):
            ans = max(ans, max(down[i], up[i]) - price[i])
        
        return ans

public class Solution {
    public long MaxOutput(int n, int[][] edges, int[] price) {
        var graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        var down = new long[n];
        var up = new long[n];
        
        void Dfs1(int u, int parent) {
            down[u] = price[u];
            foreach (int v in graph[u]) {
                if (v != parent) {
                    Dfs1(v, u);
                    down[u] = Math.Max(down[u], price[u] + down[v]);
                }
            }
        }
        
        void Dfs2(int u, int parent) {
            var childValues = new List<long>();
            foreach (int v in graph[u]) {
                if (v != parent) {
                    childValues.Add(down[v]);
                }
            }
            
            if (parent != -1) {
                childValues.Add(up[u]);
            }
            
            childValues.Sort((a, b) => b.CompareTo(a));
            
            foreach (int v in graph[u]) {
                if (v != parent) {
                    up[v] = price[u];
                    if (childValues.Count >= 2) {
                        if (down[v] == childValues[0]) {
                            up[v] = Math.Max(up[v], price[u] + childValues[1]);
                        } else {
                            up[v] = Math.Max(up[v], price[u] + childValues[0]);
                        }
                    } else if (childValues.Count == 1 && down[v] != childValues[0]) {
                        up[v] = Math.Max(up[v], price[u] + childValues[0]);
                    }
                    Dfs2(v, u);
                }
            }
        }
        
        Dfs1(0, -1);
        Dfs2(0, -1);
        
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.Max(ans, Math.Max(down[i], up[i]) - price[i]);
        }
        
        return ans;
    }
}

var maxOutput = function(n, edges, price) {
    if (n === 1) return 0;
    
    const graph = Array(n).fill(null).map(() => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    let maxCost = 0;
    
    function dfs(node, parent) {
        let max1 = 0, max2 = 0;
        
        for (const child of graph[node]) {
            if (child === parent) continue;
            
            const childMax = dfs(child, node);
            if (childMax > max1) {
                max2 = max1;
                max1 = childMax;
            } else if (childMax > max2) {
                max2 = childMax;
            }
        }
        
        maxCost = Math.max(maxCost, max1 + max2);
        return max1 + price[node];
    }
    
    function reroot(node, parent, fromParent) {
        const childValues = [];
        
        for (const child of graph[node]) {
            if (child === parent) continue;
            childValues.push(dfs(child, node));
        }
        
        childValues.sort((a, b) => b - a);
        
        let max1 = fromParent;
        let max2 = 0;
        
        for (const val of childValues) {
            if (val > max1) {
                max2 = max1;
                max1 = val;
            } else if (val > max2) {
                max2 = val;
            }
        }
        
        maxCost = Math.max(maxCost, max1 + max2);
        
        for (const child of graph[node]) {
            if (child === parent) continue;
            
            const childVal = dfs(child, node);
            let newFromParent = fromParent + price[node];
            
            for (const val of childValues) {
                if (val !== childVal) {
                    newFromParent = Math.max(newFromParent, val + price[node]);
                    break;
                }
            }
            
            reroot(child, node, newFromParent);
        }
    }
    
    const memo = new Map();
    
    function dfsMax(node, parent) {
        const key = `${node}-${parent}`;
        if (memo.has(key)) return memo.get(key);
        
        let maxPath = price[node];
        for (const child of graph[node]) {
            if (child === parent) continue;
            maxPath = Math.max(maxPath, price[node] + dfsMax(child, node));
        }
        
        memo.set(key, maxPath);
        return maxPath;
    }
    
    for (let root = 0; root < n; root++) {
        let maxPath = price[root];
        let minPath = price[root];
        
        for (const child of graph[root]) {
            const childMax = dfsMax(child, root);
            maxPath = Math.max(maxPath, childMax);
        }
        
        maxCost = Math.max(maxCost, maxPath - minPath);
    }
    
    return maxCost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(n)

时间复杂度分析：两次DFS遍历树需要O(n)时间，但在每个节点处理子节点值时需要排序，最坏情况下每个节点的度数可能达到O(n)，所以排序需要O(n log n)时间。 空间复杂度分析：需要O(n)空间存储图、down和up数组，递归调用栈深度最多为O(n)。

相关题目