3593. 最少增量使叶子路径相等

Medium

题目描述

给定一个整数 n 和一个以节点 0 为根的无向树，树有 n 个节点，编号从 0 到 n - 1。这用一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 之间有一条边。

每个节点 i 都有一个关联的代价 cost[i]，表示遍历该节点的成本。

路径的分数定义为路径上所有节点代价的总和。

你的目标是通过增加任意数量节点的代价（增加任意非负数量），使所有从根到叶子的路径分数相等。

返回必须增加代价的最少节点数量，以使所有根到叶子路径分数相等。

示例 1：

输入：n = 3, edges = [[0,1],[0,2]], cost = [2,1,3]
输出：1
解释：
有两条根到叶子路径：
- 路径 0 → 1 的分数为 2 + 1 = 3
- 路径 0 → 2 的分数为 2 + 3 = 5

为了使所有根到叶子路径分数等于 5，需要将节点 1 的代价增加 2。
只需要增加一个节点，所以输出是 1。

示例 2：

输入：n = 3, edges = [[0,1],[1,2]], cost = [5,1,4]
输出：0
解释：
只有一条根到叶子路径：
- 路径 0 → 1 → 2 的分数为 5 + 1 + 4 = 10

由于只有一条根到叶子路径，所有路径代价都相等，输出是 0。

示例 3：

输入：n = 5, edges = [[0,4],[0,1],[1,2],[1,3]], cost = [3,4,1,1,7]
输出：1
解释：
有三条根到叶子路径：
- 路径 0 → 4 的分数为 3 + 7 = 10
- 路径 0 → 1 → 2 的分数为 3 + 4 + 1 = 8
- 路径 0 → 1 → 3 的分数为 3 + 4 + 1 = 8

为了使所有根到叶子路径分数等于 10，需要将节点 1 的代价增加 2。因此，输出是 1。

约束：

2 <= n <= 10^5
edges.length == n - 1
edges[i] == [ui, vi]
0 <= ui, vi < n
cost.length == n
1 <= cost[i] <= 10^9
输入保证 edges 表示一个有效的树

解题思路

这是一个关于树形动态规划的问题。核心思想是要让所有根到叶子的路径权值相等，我们需要找到最大的路径权值作为目标值，然后计算最少需要修改多少个节点。

解题步骤：

构建树结构：根据edges构建邻接表表示的树。
找到目标值：通过DFS遍历所有根到叶子的路径，找到最大的路径权值sum，这就是我们的目标值。
计算每个节点的最小增量：对于每个节点，我们需要计算为了使通过该节点的所有根到叶子路径都达到目标值，该节点需要的最小增量。
后序遍历计算答案：从叶子节点开始向上计算。对于每个节点：
- 如果是叶子节点，其增量就是目标值减去从根到该叶子的当前路径和
- 如果是内部节点，其增量是其所有子树中需要的最大增量
统计修改节点数：当一个节点的增量与其父节点的增量不同时，说明需要修改这个节点。

关键观察：

只有当某个节点需要的增量与其父节点不同时，才需要实际增加该节点的权值
我们可以通过一次DFS计算出每个节点的最小增量需求
根节点总是需要被计算在内（除非所有路径本来就相等）

代码实现

class Solution {
public:
    int minIncrease(int n, vector<vector<int>>& edges, vector<int>& cost) {
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        long long maxPathSum = 0;
        
        function<void(int, int, long long)> findMaxPath = [&](int node, int parent, long long currentSum) {
            currentSum += cost[node];
            
            bool isLeaf = true;
            for (int child : graph[node]) {
                if (child != parent) {
                    isLeaf = false;
                    findMaxPath(child, node, currentSum);
                }
            }
            
            if (isLeaf) {
                maxPathSum = max(maxPathSum, currentSum);
            }
        };
        
        findMaxPath(0, -1, 0);
        
        int result = 0;
        
        function<long long(int, int)> dfs = [&](int node, int parent) -> long long {
            long long maxChildIncrease = 0;
            
            bool isLeaf = true;
            for (int child : graph[node]) {
                if (child != parent) {
                    isLeaf = false;
                    maxChildIncrease = max(maxChildIncrease, dfs(child, node));
                }
            }
            
            long long nodeIncrease = maxChildIncrease;
            if (isLeaf) {
                // For leaf nodes, calculate the increase needed
                long long pathSum = 0;
                int curr = node;
                int par = parent;
                
                function<void(int, int, long long)> calculatePath = [&](int n, int p, long long sum) {
                    sum += cost[n];
                    if (n == node) {
                        pathSum = sum;
                        return;
                    }
                    for (int child : graph[n]) {
                        if (child != p) {
                            calculatePath(child, n, sum);
                            if (pathSum != 0) return;
                        }
                    }
                };
                
                calculatePath(0, -1, 0);
                nodeIncrease = maxPathSum - pathSum;
            }
            
            if (parent == -1 || nodeIncrease != maxChildIncrease) {
                result++;
            }
            
            return nodeIncrease;
        };
        
        dfs(0, -1);
        return result;
    }
};

class Solution:
    def minIncrease(self, n: int, edges: List[List[int]], cost: List[int]) -> int:
        from collections import defaultdict
        
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        max_path_sum = 0
        
        def find_max_path(node, parent, current_sum):
            nonlocal max_path_sum
            current_sum += cost[node]
            
            is_leaf = True
            for child in graph[node]:
                if child != parent:
                    is_leaf = False
                    find_max_path(child, node, current_sum)
            
            if is_leaf:
                max_path_sum = max(max_path_sum, current_sum)
        
        find_max_path(0, -1, 0)
        
        result = 0
        
        def dfs(node, parent):
            nonlocal result
            
            max_child_increase = 0
            is_leaf = True
            
            for child in graph[node]:
                if child != parent:
                    is_leaf = False
                    max_child_increase = max(max_child_increase, dfs(child, node))
            
            if is_leaf:
                # Calculate path sum from root to this leaf
                def get_path_sum(curr, par, current_sum):
                    current_sum += cost[curr]
                    if curr == node:
                        return current_sum
                    
                    for child in graph[curr]:
                        if child != par:
                            path_sum = get_path_sum(child, curr, current_sum)
                            if path_sum != -1:
                                return path_sum
                    return -1
                
                path_sum = get_path_sum(0, -1, 0)
                node_increase = max_path_sum - path_sum
            else:
                node_increase = max_child_increase
            
            if parent == -1 or node_increase != max_child_increase:
                result += 1
            
            return node_increase
        
        dfs(0, -1)
        return result

public class Solution {
    public int MinIncrease(int n, int[][] edges, int[] cost) {
        List<int>[] 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]);
        }
        
        long maxPathSum = 0;
        
        void FindMaxPath(int node, int parent, long currentSum) {
            currentSum += cost[node];
            
            bool isLeaf = true;
            foreach (int child in graph[node]) {
                if (child != parent) {
                    isLeaf = false;
                    FindMaxPath(child, node, currentSum);
                }
            }
            
            if (isLeaf) {
                maxPathSum = Math.Max(maxPathSum, currentSum);
            }
        }
        
        FindMaxPath(0, -1, 0);
        
        int result = 0;
        
        long DFS(int node, int parent) {
            long maxChildIncrease = 0;
            bool isLeaf = true;
            
            foreach (int child in graph[node]) {
                if (child != parent) {
                    isLeaf = false;
                    maxChildIncrease = Math.Max(maxChildIncrease, DFS(child, node));
                }
            }
            
            long nodeIncrease;
            if (isLeaf) {
                long GetPathSum(int curr, int par, long currentSum) {
                    currentSum += cost[curr];
                    if (curr == node) {
                        return currentSum;
                    }
                    
                    foreach (int child in graph[curr]) {
                        if (child != par) {
                            long pathSum = GetPathSum(child, curr, currentSum);
                            if (pathSum != -1) {
                                return pathSum;
                            }
                        }
                    }
                    return -1;
                }
                
                long pathSum = GetPathSum(0, -1, 0);
                nodeIncrease = maxPathSum - pathSum;
            } else {
                nodeIncrease = maxChildIncrease;
            }
            
            if (parent == -1 || nodeIncrease != maxChildIncrease) {
                result++;
            }
            
            return nodeIncrease;
        }
        
        DFS(0, -1);
        return result;
    }
}

var minIncrease = function(n, edges, cost) {
    const adj = Array(n).fill().map(() => []);
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
    }
    
    let result = 0;
    
    function dfs(node, parent) {
        const children = adj[node].filter(child => child !== parent);
        
        if (children.length === 0) {
            return cost[node];
        }
        
        const childScores = children.map(child => dfs(child, node));
        const maxScore = Math.max(...childScores);
        
        for (const score of childScores) {
            if (score < maxScore) {
                result++;
            }
        }
        
        return cost[node] + maxScore;
    }
    
    dfs(0, -1);
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n²)	需要遍历树两次，每次叶子节点都要计算到根的路径
空间复杂度	O(n)	递归调用栈和图的存储空间

题目描述#

解题思路#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

解题思路

代码实现

复杂度分析