2440-创建价值相同的连通块

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:07 2023-09-13 17:01:07 Updated    

有一棵 n 个节点的无向树，节点编号为 0 到 n - 1 。

给你一个长度为 n 下标从 0 开始的整数数组 nums ，其中 nums[i] 表示第 i 个节点的值。同时给你一个长度为 `n

  • 1的二维整数数组edges，其中edges[i] = [ai, bi]表示节点ai与bi` 之间有一条边。

你可以 删除 一些边，将这棵树分成几个连通块。一个连通块的 价值 定义为这个连通块中 所有 节点 i 对应的
nums[i] 之和。

你需要删除一些边，删除后得到的各个连通块的价值都相等。请返回你可以删除的边数 最多 为多少。

示例 1：

**输入：** nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]] 
**输出：** 2 
**解释：** 上图展示了我们可以删除边 [0,1] 和 [3,4] 。得到的连通块为 [0] ，[1,2,3] 和 [4] 。每个连通块的价值都为 6 。可以证明没有别的更好的删除方案存在了，所以答案为 2 。

示例 2：

**输入：** nums = [2], edges = []
**输出：** 0
**解释：** 没有任何边可以删除。

提示：

  • 1 <= n <= 2 * 104
  • nums.length == n
  • 1 <= nums[i] <= 50
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= edges[i][0], edges[i][1] <= n - 1
  • edges 表示一棵合法的树。

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场双周赛的看法~

提示 1

枚举连通块的个数 i，则删除的边数为 i-1。

设 total 为所有 nums}[i] 的和，如果 total 能被 i 整除（i 是 total 的因子），那么每个连通块的价值都应等于 \dfrac{\textit{total} }{i，记作 target。

如何判定存在这些连通块呢？

提示 2

如果一颗子树的价值等于 target，那么可以将其作为一个连通块，和其父节点断开，换句话说，它对其祖先节点的价值贡献是 0。

DFS 这棵树，统计子树的价值：

  • 如果价值超过 target，那么当前删边方案不合法，返回 -1。
  • 如果价值等于 target，找到了一个连通块，和其父节点断开，返回 0。
  • 如果价值小于 target，尚未找到一个完整的连通块，返回价值。

如果 DFS 完了没有返回 -1，则当前删边方案合法。如果从大到小枚举连通块的个数，则此时可以直接返回答案。

优化

代码实现时，由于价值至少为 \max(\textit{nums}[i])，连通块的个数至多为 \left\lfloor\dfrac{\textit{total} }{\max(\textit{nums}[i])}\right\rfloor。由于 \left\lfloor\dfrac{\textit{total} }{\max(\textit{nums}[i])}\right\rfloor\le n，因此可以从 \left\lfloor\dfrac{\textit{total} }{\max(\textit{nums}[i])}\right\rfloor 开始枚举连通块的个数。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:
        g = [[] for _ in nums]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        def dfs(x: int, fa: int) -> int:
            s = nums[x]  # 价值
            for y in g[x]:
                if y != fa:
                    res = dfs(y, x)
                    if res < 0: return -1
                    s += res
            if s > target: return -1
            return s if s < target else 0

        total = sum(nums)
        for i in range(total // max(nums), 1, -1):
            if total % i == 0:
                target = total // i
                if dfs(0, -1) == 0: return i - 1
        return 0
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    private List<Integer>[] g;
    private int[] nums;
    private int target;

    public int componentValue(int[] nums, int[][] edges) {
        g = new ArrayList[nums.length];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        this.nums = nums;

        var total = Arrays.stream(nums).sum();
        var max = Arrays.stream(nums).max().orElseThrow();
        for (var i = total / max; ; --i)
            if (total % i == 0) {
                target = total / i;
                if (dfs(0, -1) == 0) return i - 1;
            }
    }

    private int dfs(int x, int fa) {
        var sum = nums[x]; // 价值
        for (var y : g[x])
            if (y != fa) {
                var res = dfs(y, x);
                if (res < 0) return -1;
                sum += res;
            }
        if (sum > target) return -1;
        return sum < target ? sum : 0;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int componentValue(vector<int> &nums, vector<vector<int>> &edges) {
        vector<vector<int>> g(nums.size());
        for (auto &e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        int target;
        function<int(int, int)> dfs = [&](int x, int fa) {
            int sum = nums[x]; // 价值
            for (int y : g[x])
                if (y != fa) {
                    int res = dfs(y, x);
                    if (res < 0) return -1;
                    sum += res;
                }
            if (sum > target) return -1;
            return sum < target ? sum : 0;
        };

        int total = accumulate(nums.begin(), nums.end(), 0);
        int mx = *max_element(nums.begin(), nums.end());
        for (int i = total / mx;; --i)
            if (total % i == 0) {
                target = total / i;
                if (dfs(0, -1) == 0) return i - 1;
            }
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
func componentValue(nums []int, edges [][]int) int {
	g := make([][]int, len(nums))
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x)
	}

	var target int
	var dfs func(int, int) int
	dfs = func(x, fa int) int {
		sum := nums[x] // 价值
		for _, y := range g[x] {
			if y != fa {
				res := dfs(y, x)
				if res < 0 {
					return -1
				}
				sum += res
			}
		}
		if sum > target {
			return -1
		}
		if sum == target {
			return 0
		}
		return sum
	}

	total, mx := 0, 0
	for _, x := range nums {
		total += x
		mx = max(mx, x)
	}
	for i := total / mx; ; i-- {
		if total%i == 0 {
			target = total / i
			if dfs(0, -1) == 0 {
				return i - 1
			}
		}
	}
}

func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

  • 时间复杂度：O(n\cdot d(s))，其中 n 为 nums 的长度，s 为所有 nums}[i] 的和，d(s) 为 s 的因子个数。根据本题的数据范围，d(s)\le 240，s=720720 时取等号。
  • 空间复杂度：O(n)。当树是一条链时，递归的深度最大为 n，需要的栈空间为 O(n)。
 Comments
On this page
2440-创建价值相同的连通块