Luobuyu's Blog

0%

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

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.9k 阅读时长 ≈ 2 分钟
直接贪心删除边就行。

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

题目描述：

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

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

你可以从树中删除一些边，也可以一条边也不删，得到若干连通块。一个 连通块的值 定义为连通块中所有节点值之和。如果所有连通块的值都可以被 k 整除，那么我们说这是一个 合法分割 。

请你返回所有合法分割中，连通块数目的最大值 。

数据范围：

$1\le n \le 3\times 10^4;1\le k \le 10^9$

保证所有蒜素之和可以被 $k$ 整除。

题解：

因为保证了元素之和可以被 $k$ 整除。因此只需要每次遇到能被整除的子树，直接删除就行。剩余的元素之和还是能被 $k$ 整除的。

计算每个子树的权值之和，如果子树的权值之和能被 $k$ 整除，就对答案加 $1$ 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int n, k;
    int ans = 0;
    vector<vector<int>> g;
    vector<int> values;
    vector<int> dp;
    void dfs(int u, int fa)
    {
        dp[u] = values[u];
        for (int i = 0; i < g[u].size(); ++i)
        {
            int v = g[u][i];
            if (v == fa)
                continue;
            dfs(v, u);
            if (dp[v] % k != 0)
            {
                dp[u] += dp[v];
            }
        }
        if (dp[u] % k == 0)
            ans++;
    }
    int maxKDivisibleComponents(int _n, vector<vector<int>> &edges, vector<int> &_values, int _k)
    {
        n = _n;
        k = _k;
        g.resize(n);
        dp.resize(n);
        values = _values;
        for (auto &edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            g[u].emplace_back(v);
            g[v].emplace_back(u);
        }
        dfs(0, -1);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int n, k;
    int ans = 0;
    vector<vector<int>> g;
    vector<int> values;
    int dfs(int u, int fa)
    {
        int sum = values[u];
        for (int i = 0; i < g[u].size(); ++i)
        {
            int v = g[u][i];
            if (v == fa)
                continue;
            sum = (sum + dfs(v, u)) % k;
        }
        if(sum % k == 0) ans++;
        return sum;
    }
    int maxKDivisibleComponents(int _n, vector<vector<int>> &edges, vector<int> &_values, int _k)
    {
        n = _n;
        k = _k;
        g.resize(n);
        values = _values;
        for (auto &edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            g[u].emplace_back(v);
            g[v].emplace_back(u);
        }
        dfs(0, -1);
        return ans;
    }
};