题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个无向树，共 n 个节点，每个节点编号 0到n-1，再给一个数字k，整个树之和能被 k 整除，现在要尽可能地把树划分成多个连通块，每个块的和也能被 k 整除。

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:
        f = [[] for _ in range(n)]
        for x, y in edges:
            f[x].append(y)
            f[y].append(x)

        # 从父节点 fa 进入 i 的连通区域之和
        def dfs(i:int, fa:int) -> int:
            cur_sum = values[i]
            for j in f[i]:
                if j != fa:
                    cur_sum += dfs(j, i)
            nonlocal ans
            if cur_sum % k == 0:
                ans += 1
            return cur_sum
        ans = 0
        dfs(0, -1)
        return ans