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

给你一棵 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;
    }
};

二. 树形dp

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;
    }
};