LeetCode 2872. 可以被 K 整除连通块的最大数目
原题链接
困难
作者:
我是java同学
,
2023-10-03 17:53:15
,
所有人可见
,
阅读 62
class Solution {
public:
int res, k;
vector<vector<int>> g;
vector<int> values;
typedef long long LL;
LL dfs(int u, int fa) {
LL sum = values[u];
for (auto& v: g[u])
if (v != fa)
sum += dfs(v, u);
if (sum % k == 0) res ++ ;
return sum;
}
int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& _values, int _k) {
g.resize(n);
k = _k;
values = _values;
for (auto e: edges) {
int a = e[0], b = e[1];
g[a].push_back(b);
g[b].push_back(a);
}
dfs(0, -1);
return res;
}
};