Hard

题目描述

有一个包含 n 个节点的无向树，节点编号从 0 到 n - 1。

给你一个长度为 n 的下标从 0 开始的整数数组 nums，其中 nums[i] 表示第 i 个节点的值。还给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。

你可以删除一些边，将树分割成多个连通分量。连通分量的价值是该分量中所有 nums[i] 的总和，其中 i 是该分量中的节点。

返回你最多可以删除的边数，使得剩余的每个连通分量都有相同的价值。

示例 1：

输入: nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]]
输出: 2
解释: 上图展示了如何删除边 [0,1] 和 [3,4]。创建的分量为节点 [0]，[1,2,3] 和 [4]。每个分量中值的总和都等于 6。可以证明不存在更好的删除方案，所以答案是 2。

示例 2：

输入: nums = [2], edges = []
输出: 0
解释: 没有边可以删除。

约束条件：

  • 1 <= n <= 2 * 10^4
  • nums.length == n
  • 1 <= nums[i] <= 50
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= edges[i][0], edges[i][1] <= n - 1
  • edges 表示一个有效的树

解题思路

这是一道经典的树上分割问题。核心思路是枚举所有可能的连通分量价值，然后验证是否能通过删除边来实现。

主要思路：

  1. 价值枚举：如果最终有 k 个连通分量，每个分量的价值为 target，那么 k × target = sum（总价值）。因此我们需要枚举 sum 的所有约数作为可能的 target。

  2. DFS验证：对于每个 target，使用DFS来验证是否能够分割树。DFS过程中，对于每个节点计算以它为根的子树的价值总和：

    • 如果子树价值等于 target，说明可以在此处切断，返回 0
    • 如果子树价值小于 target，返回当前价值继续向上累加
    • 如果子树价值大于 target，说明无法分割，返回 -1

  3. 最优解计算：能够分割成功的情况下，连通分量数为 sum / target，删除的边数为 (sum / target) - 1。

算法流程：

  • 计算所有节点价值总和 sum
  • 枚举 sum 的所有约数（从大到小，优先找最优解）
  • 对每个约数使用DFS验证是否可行
  • 返回最大的删除边数

时间复杂度主要由约数枚举和每次DFS验证构成。

代码实现

class Solution {
public:
    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        if (n == 1) return 0;
        
        // Build adjacency list
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        
        // Try all possible component values (divisors of totalSum)
        for (int components = n; components >= 2; components--) {
            if (totalSum % components != 0) continue;
            
            int target = totalSum / components;
            
            // Check if we can split into 'components' parts with value 'target' each
            if (canSplit(graph, nums, target, 0, -1) == 0) {
                return components - 1;
            }
        }
        
        return 0;
    }
    
private:
    // Returns: sum of subtree rooted at node, or -1 if impossible, or 0 if subtree equals target
    int canSplit(vector<vector<int>>& graph, vector<int>& nums, int target, int node, int parent) {
        int sum = nums[node];
        
        for (int neighbor : graph[node]) {
            if (neighbor == parent) continue;
            
            int childSum = canSplit(graph, nums, target, neighbor, node);
            if (childSum == -1) return -1;
            
            sum += childSum;
        }
        
        if (sum == target) return 0;
        if (sum < target) return sum;
        return -1;  // sum > target, impossible
    }
};

class Solution:
    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        
        # Build adjacency list
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        total_sum = sum(nums)
        
        def can_split(node, parent, target):
            """
            Returns: sum of subtree rooted at node, or -1 if impossible, or 0 if subtree equals target
            """
            curr_sum = nums[node]
            
            for neighbor in graph[node]:
                if neighbor == parent:
                    continue
                
                child_sum = can_split(neighbor, node, target)
                if child_sum == -1:
                    return -1
                
                curr_sum += child_sum
            
            if curr_sum == target:
                return 0
            elif curr_sum < target:
                return curr_sum
            else:
                return -1
        
        # Try all possible number of components (from n down to 2)
        for components in range(n, 1, -1):
            if total_sum % components != 0:
                continue
            
            target = total_sum // components
            
            # Check if we can split into 'components' parts with value 'target' each
            if can_split(0, -1, target) == 0:
                return components - 1
        
        return 0

public class Solution {
    public int ComponentValue(int[] nums, int[][] edges) {
        int n = nums.Length;
        if (n == 1) return 0;
        
        // Build adjacency list
        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]);
        }
        
        int totalSum = nums.Sum();
        
        // Try all possible number of components (from n down to 2)
        for (int components = n; components >= 2; components--) {
            if (totalSum % components != 0) continue;
            
            int target = totalSum / components;
            
            // Check if we can split into 'components' parts with value 'target' each
            if (CanSplit(graph, nums, target, 0, -1) == 0) {
                return components - 1;
            }
        }
        
        return 0;
    }
    
    private int CanSplit(List<int>[] graph, int[] nums, int target, int node, int parent) {
        int sum = nums[node];
        
        foreach (int neighbor in graph[node]) {
            if (neighbor == parent) continue;
            
            int childSum = CanSplit(graph, nums, target, neighbor, node);
            if (childSum == -1) return -1;
            
            sum += childSum;
        }
        
        if (sum == target) return 0;
        if (sum < target) return sum;
        return -1;  // sum > target, impossible
    }
}

var componentValue = function(nums, edges) {
    const n = nums.length;
    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);
    }
    
    const totalSum = nums.reduce((sum, val) => sum + val, 0);
    
    for (let components = n; components >= 2; components--) {
        if (totalSum % components !== 0) continue;
        
        const targetSum = totalSum / components;
        let removedEdges = 0;
        
        const dfs = (node, parent) => {
            let subtreeSum = nums[node];
            
            for (const child of graph[node]) {
                if (child === parent) continue;
                
                const childSum = dfs(child, node);
                if (childSum === targetSum) {
                    removedEdges++;
                } else {
                    subtreeSum += childSum;
                }
            }
            
            return subtreeSum;
        };
        
        const rootSum = dfs(0, -1);
        if (rootSum === targetSum && removedEdges === components - 1) {
            return removedEdges;
        }
    }
    
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(d(sum) × n)，其中 d(sum) 是 sum 的约数个数，通常约数个数很少
空间复杂度O(n)，用于存储图的邻接表和递归调用栈

相关题目