2872. 可以被 K 整除連通塊的最大数目

思路

題目保證整顆樹的數值總和是k的倍數，這讓寫程式方便了很多。
現在要讓這顆樹盡量分割為越多塊越好，並且每塊總和也都是k的倍數。

建立一個函數dfs(node, parentNode)，代表以node為根結點，往下看的數值總和，
紀錄parentNode的原因是為了避免在走訪鄰居時走回頭路。

因為整樹總和sum % k = 0，當找到了數值總和為k倍數的子節點，
也就是滿足dfs(node, parentNode) % k = 0時，這段就能獨立成一塊。

因為(sum - dfs(node, parentNode)) % k 同樣為 0，
因此切分之後，不會讓被切開的節點變得不滿足條件。

遞迴對這一塊再去找滿足條件的子節點，紀錄切分次數，即為所求。

程式碼

dfs

class Solution {
public:
    int maxKDivisibleComponents(int n, vector<vector<int>> &edges,vector<int> &values, int k)
    {
        // 紀錄鄰居
        vector<int> adj(n);
        for (auto edge : edges)
        {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        int res = 0;
        // dfs(curNode, parentNode) 表示從 curNode 往下看的和
        auto dfs = [&](int curNode, int parentNode) -> int {
            int sum = 0;
            for(auto neighbor : adj[curNode]) {
                if(neighbor != parentNode) {
                    sum += dfs(neighbor, curNode);
                    sum %= k;
                }
                sum += values[curNode];
            }
            sum += values[curNode];
            sum %= k;
            if(sum == 0) ++res;
            return sum;
        };
        dfs(0, -1);
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$