Hard

题目描述

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

同时给你一个下标从 0 开始、长度为 n 的整数数组 values，其中 values[i] 是第 i 个节点的值，以及一个整数 k。

树的一个有效分割是通过移除树中的任意一组边（可能为空）得到的，使得生成的所有连通组件的值都能被 k 整除，其中一个连通组件的值是其节点值的和。

返回任何有效分割中组件的最大数量。

示例 1：

输入：n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6
输出：2
解释：我们移除连接节点 1 和 2 的边。得到的分割是有效的，因为：
- 包含节点 1 和 3 的组件的值为 values[1] + values[3] = 12。
- 包含节点 0、2 和 4 的组件的值为 values[0] + values[2] + values[4] = 6。
可以证明没有其他有效分割有超过 2 个连通组件。

示例 2：

输入：n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [3,0,6,1,5,2,1], k = 3
输出：3
解释：我们移除连接节点 0 和 2 的边，以及连接节点 0 和 1 的边。得到的分割是有效的，因为：
- 包含节点 0 的组件的值为 values[0] = 3。
- 包含节点 2、5 和 6 的组件的值为 values[2] + values[5] + values[6] = 9。
- 包含节点 1、3 和 4 的组件的值为 values[1] + values[3] + values[4] = 6。
可以证明没有其他有效分割有超过 3 个连通组件。

提示：

  • 1 <= n <= 3 * 10^4
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • values.length == n
  • 0 <= values[i] <= 10^9
  • 1 <= k <= 10^9
  • 所有值的总和能被 k 整除
  • 输入保证 edges 表示一棵有效的树

解题思路

这是一道关于树上动态规划的问题。核心思路是通过深度优先搜索（DFS）来计算每个子树的节点值总和，然后判断是否可以将其分割为独立的组件。

解题思路：

  1. 建图：根据给定的边构建邻接表表示的无向树。

  2. DFS策略：从任意节点（通常选择节点0）开始进行DFS遍历。对于每个节点，我们需要计算以该节点为根的子树的总和。

  3. 分割判断：在DFS过程中，对于每个节点，我们检查其子树的总和是否能被k整除。如果某个子树的总和能被k整除，那么我们可以将这个子树作为一个独立的组件分割出来，此时组件数量加1。

  4. 状态传递：如果子树总和能被k整除，我们就将其分割出来，向父节点返回0（表示这部分已经被分割）；否则，向父节点返回子树的实际总和。

  5. 最终统计：最后剩余的部分（包含根节点的组件）也算作一个组件。

关键洞察：

  • 如果一个子树的节点值总和能被k整除，那么最优策略就是将其分割为独立组件
  • 贪心策略：尽可能多地分割出能被k整除的子树
  • 由于题目保证所有节点值的总和能被k整除，所以最终方案一定是有效的

代码实现

class Solution {
public:
    int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) {
        if (n == 1) return 1;
        
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        int components = 0;
        
        function<long long(int, int)> dfs = [&](int node, int parent) -> long long {
            long long sum = values[node];
            
            for (int neighbor : graph[node]) {
                if (neighbor != parent) {
                    sum += dfs(neighbor, node);
                }
            }
            
            if (sum % k == 0) {
                components++;
                return 0;
            }
            
            return sum;
        };
        
        dfs(0, -1);
        return components;
    }
};

class Solution:
    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:
        if n == 1:
            return 1
        
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        self.components = 0
        
        def dfs(node, parent):
            total = values[node]
            
            for neighbor in graph[node]:
                if neighbor != parent:
                    total += dfs(neighbor, node)
            
            if total % k == 0:
                self.components += 1
                return 0
            
            return total
        
        dfs(0, -1)
        return self.components

public class Solution {
    private int components = 0;
    
    public int MaxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
        if (n == 1) return 1;
        
        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]);
        }
        
        components = 0;
        DFS(0, -1, graph, values, k);
        return components;
    }
    
    private long DFS(int node, int parent, List<int>[] graph, int[] values, int k) {
        long sum = values[node];
        
        foreach (int neighbor in graph[node]) {
            if (neighbor != parent) {
                sum += DFS(neighbor, node, graph, values, k);
            }
        }
        
        if (sum % k == 0) {
            components++;
            return 0;
        }
        
        return sum;
    }
}

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number[]} values
 * @param {number} k
 * @return {number}
 */
var maxKDivisibleComponents = function(n, edges, values, k) {
    if (n === 1) return 1;
    
    // Build adjacency list
    const adj = Array(n).fill().map(() => []);
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
    }
    
    let components = 0;
    
    function dfs(node, parent) {
        let subtreeSum = values[node];
        
        for (const neighbor of adj[node]) {
            if (neighbor !== parent) {
                subtreeSum += dfs(neighbor, node);
            }
        }
        
        if (subtreeSum % k === 0) {
            components++;
            return 0;
        }
        
        return subtreeSum;
    }
    
    dfs(0, -1);
    return components;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历树的每个节点一次
空间复杂度O(n)需要存储图的邻接表和递归调用栈

相关题目