Re: [闲聊] 每日leetcode

楼主: dont   2024-12-21 10:13:27
2872. Maximum Number of K-Divisible Components
## 思路
建Graph, DFS 计算/回传 节点+子节点总和%k的值
如果加总为0 表示可以分割: res+1
## Code
```python
class Solution:
def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values:
List[int], k: int) -> int:
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
def dfs(node, parent):
nonlocal res
val = values[node]
for child in graph[node]:
if child == parent:
continue
val += dfs(child, node)
val %= k
if val == 0:
res += 1
return val
res = 0
dfs(0, None)
return res
```

Links booklink

Contact Us: admin [ a t ] ucptt.com