可以被 K 整除连通块的最大数目

2872. 可以被 K 整除连通块的最大数目

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

同时给你一个下标从 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⁴
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
values.length == n
0 <= values[i] <= 10⁹
1 <= k <= 10⁹
values 之和可以被 k 整除。
输入保证 edges 是一棵无向树。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) { } };

golang 解法, 执行用时: 212 ms, 内存消耗: 14.4 MB, 提交时间: 2023-10-02 00:09:49

func maxKDivisibleComponents(n int, edges [][]int, values []int, k int) (ans int) {
	g := make([][]int, n)
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x)
	}
	var dfs func(int, int) int
	dfs = func(x, fa int) int {
		s := values[x]
		for _, y := range g[x] {
			if y != fa {
				s += dfs(y, x)
			}
		}
		if s%k == 0 {
			ans++
		}
		return s
	}
	dfs(0, -1)
	return
}

java 解法, 执行用时: 26 ms, 内存消耗: 56.8 MB, 提交时间: 2023-10-02 00:09:36

class Solution {
    private List<Integer>[] g;
    private int[] values;
    private int k, ans;

    public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        this.values = values;
        this.k = k;
        dfs(0, -1);
        return ans;
    }

    private long dfs(int x, int fa) {
        long sum = values[x];
        for (int y : g[x]) {
            if (y != fa) {
                sum += dfs(y, x);
            }
        }
        ans += sum % k == 0 ? 1 : 0;
        return sum;
    }
}

cpp 解法, 执行用时: 348 ms, 内存消耗: 176.1 MB, 提交时间: 2023-10-02 00:09:22

class Solution {
public:
    int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) {
        vector<vector<int>> g(n);
        for (auto &e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        int ans = 0;
        function<long long(int, int)> dfs = [&](int x, int fa) -> long long {
            long long sum = values[x];
            for (int y : g[x])
                if (y != fa)
                    sum += dfs(y, x);
            ans += sum % k == 0;
            return sum;
        };
        dfs(0, -1);
        return ans;
    }
};

python3 解法, 执行用时: 236 ms, 内存消耗: 58.7 MB, 提交时间: 2023-10-02 00:09:11

'''
如果一条边左右两侧的点权和都是 k 的倍数，那么这条边就可以删除。由于题目保证 values 之和可以被 k 整除。
那么只需要看一侧的点权和是否为 k 的倍数。实现时，可以从任意点出发 DFS，
只要发现子树的点权和是 k 的倍数，就说明子树到上面父节点的这条边是可以删除的。
'''
class Solution:
    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        ans = 0
        def dfs(x: int, fa: int) -> int:
            s = values[x]
            for y in g[x]:
                if y != fa:
                    s += dfs(y, x)
            nonlocal ans
            ans += s % k == 0
            return s
        dfs(0, -1)
        return ans

上一题

下一题

详情