可以被K整除连通块的最大数目-526互联

给你一棵 n 个节点的无向树，节点编号为 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 有一条边
同时给你一个下标从 0 开始长度为 n 的整数数组 values ，其中 values[i] 是第 i 个节点的值。再给你一个整数 k
你可以从树中删除一些边，也可以一条边也不删，得到若干连通块。一个连通块的值定义为连通块中所有节点值之和。如果所有连通块的值都可以被 k 整除，那么我们说这是一个合法分割
请你返回所有合法分割中，连通块数目的最大值

一. 贪心分割

class Solution {
public:
    int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) {
        //贪心进行分割，如果子树满足条件，子树中某个叶子节点也满足条件，那这颗子树必然可以进行再划分
        //所以可以选择贪心从叶子节点进行分割
        unordered_set<int> s[n];

        for(auto &edge:edges){
            s[edge[0]].insert(edge[1]);
            s[edge[1]].insert(edge[0]);
        }
        queue<int> q;
        for(int i=0;i<n;i++)
            if(s[i].size()==1||s[i].size()==0) q.push(i);
        int cnt = 0;
        while(!q.empty()){
            int cur = q.front(); q.pop();
            if(values[cur]%k==0) cnt++;
            for(auto next:s[cur]){//遍历领接边
                s[next].erase(cur);//删除关系
                if(s[next].size()==1)    q.push(next);
                if(values[cur]%k!=0) values[next]+=values[cur];
            }
        }
        return cnt;
    }
};

数目