题目描述
给你一棵 n
个节点的无向树,节点编号为 0
到 n - 1
。给你整数 n
和一个长度为 n - 1
的二维整数数组 edges
,其中 edges[i] = [a_i, b_i]
表示树中节点 a_i
和 b_i
有一条边。
同时给你一个下标从 0 开始长度为 n
的整数数组 values
,其中 values[i]
是第 i
个节点的 值。再给你一个整数 k
。
你可以从树中删除一些边,也可以一条边也不删,得到若干连通块。一个 连通块的值 定义为连通块中所有节点值之和。如果所有连通块的值都可以被 k
整除,那么我们说这是一个 合法分割。
请你返回所有合法分割中,连通块数目的最大值。
样例
输入:n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6
输出:2
解释:我们删除节点 1 和 2 之间的边。这是一个合法分割,因为:
- 节点 1 和 3 所在连通块的值为 values[1] + values[3] = 12。
- 节点 0,2 和 4 所在连通块的值为 values[0] + values[2] + values[4] = 6。
最多可以得到 2 个连通块的合法分割。
输入:n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [3,0,6,1,5,2,1], k = 3
输出:3
解释:我们删除节点 0 和 2 ,以及节点 0 和 1 之间的边。这是一个合法分割,因为:
- 节点 0 的连通块的值为 values[0] = 3 。
- 节点 2,5 和 6 所在连通块的值为 values[2] + values[5] + values[6] = 9。
- 节点 1,3 和 4 的连通块的值为 values[1] + values[3] + values[4] = 6。
最多可以得到 3 个连通块的合法分割。
限制
1 <= n <= 3 * 10^4
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
values.length == n
0 <= values[i] <= 10^9
1 <= k <= 10^9
values
之和可以被k
整除。- 输入保证
edges
是一棵无向树。
算法
(深度优先遍历) $O(n)$
- 从 $0$ 节点深度优先遍历,自底向上计算答案,递归返回当前连通块模 $k$ 后的结果。
- 递归开始时初始变量 $tot$ 为当前节点的值,然后遍历所有子节点,累加子节点的返回值 $ret$。
- 如果 $tot$ 模 $k$ 等于 $0$,则说明这个连通块可以独立存在,断开当前根节点与父节点的连接,并返回 $0$。
- 否则,返回 $tot$ 模 $k$ 的值,需要与父节点连通。
时间复杂度
- 每个节点仅被遍历一次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储图和递归的系统栈。
C++ 代码
class Solution {
private:
int ans;
vector<vector<int>> graph;
int dfs(int u, int fa, const vector<int> &values, int k) {
int tot = values[u] % k;
for (int v : graph[u]) {
if (v == fa)
continue;
int ret = dfs(v, u, values, k);
tot = (tot + ret) % k;
}
if (tot == 0)
++ans;
return tot;
}
public:
int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) {
graph.resize(n);
for (const auto &e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
ans = 0;
dfs(0, -1, values, k);
return ans;
}
};