2322-从树中删除边的最小分数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

存在一棵无向连通树，树中有编号从 0 到 n - 1 的 n 个节点， 以及 n - 1 条边。

给你一个下标从 0 开始的整数数组 nums ，长度为 n ，其中 nums[i] 表示第 i 个节点的值。另给你一个二维整数数组
edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中存在一条位于节点 ai 和 bi 之间的边。

删除树中两条 不同 的边以形成三个连通组件。对于一种删除边方案，定义如下步骤以计算其分数：

  1. 分别获取三个组件 每个 组件中所有节点值的异或值。
  2. 最大 异或值和 最小 异或值的 差值 就是这一种删除边方案的分数。
  • 例如，三个组件的节点值分别是：[4,5,7]、[1,9] 和 [3,3,3] 。三个异或值分别是 4 ^ 5 ^ 7 = _**6**_、1 ^ 9 = _**8**_ 和 3 ^ 3 ^ 3 = _**3**_ 。最大异或值是 8 ，最小异或值是 3 ，分数是 8 - 3 = 5 。

返回在给定树上执行任意删除边方案可能的 最小 分数。

示例 1：

**输入：** nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
**输出：** 9
**解释：** 上图展示了一种删除边方案。
- 第 1 个组件的节点是 [1,3,4] ，值是 [5,4,11] 。异或值是 5 ^ 4 ^ 11 = 10 。
- 第 2 个组件的节点是 [0] ，值是 [1] 。异或值是 1 = 1 。
- 第 3 个组件的节点是 [2] ，值是 [5] 。异或值是 5 = 5 。
分数是最大异或值和最小异或值的差值，10 - 1 = 9 。
可以证明不存在分数比 9 小的删除边方案。

示例 2：

**输入：** nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
**输出：** 0
**解释：** 上图展示了一种删除边方案。
- 第 1 个组件的节点是 [3,4] ，值是 [4,4] 。异或值是 4 ^ 4 = 0 。
- 第 2 个组件的节点是 [1,0] ，值是 [5,5] 。异或值是 5 ^ 5 = 0 。
- 第 3 个组件的节点是 [2,5] ，值是 [2,2] 。异或值是 2 ^ 2 = 0 。
分数是最大异或值和最小异或值的差值，0 - 0 = 0 。
无法获得比 0 更小的分数 0 。

提示：

  • n == nums.length
  • 3 <= n <= 1000
  • 1 <= nums[i] <= 108
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges 表示一棵有效的树

本题 视频讲解 已出炉，欢迎点赞三连~

何为时间戳？

我们可以在 DFS 一棵树的过程中，维护一个全局的时间戳 clock，每访问一个新的节点，就将 clock 加一。同时，记录进入节点 x 时的时间戳 in}[x]，和离开（递归结束）这个节点时的时间戳 out}[x]。

时间戳有什么性质？

根据 DFS 的性质，当我们递归以 x 为根的子树时，设 y 是 x 的子孙节点，我们必须先递归完以 y 为根的子树，之后才能递归完以 x 为根的子树。

从时间戳上看，如果 y 是 x 的子孙节点，那么区间 [\textit{in}[y],\textit{out}[y]] 必然被区间 [\textit{in}[x],\textit{out}[x]] 所包含。

反之，如果区间 [\textit{in}[y],\textit{out}[y]] 被区间 [\textit{in}[x],\textit{out}[x]] 所包含，那么 y 必然是 x 的子孙节点（换句话说 x 是 y 的祖先节点）。因此我们可以通过

\textit{in}[x]<\textit{in}[y]\le\textit{out}[y]\le\textit{out}[x]

来判断 x 是否为 y 的祖先节点，由于 in}[y]\le\textit{out}[y] 恒成立，上式可以简化为

\textit{in}[x]<\textit{in}[y]\le\textit{out}[x]

回到本题。由于需要求出子树的异或和，不妨以 0 为根，DFS 这棵树，在求出时间戳的同时，求出每棵以 x 为根的子树的异或和 xor}[x]。

由于 n 比较小，我们可以用 O(n^2) 的时间枚举要删除的两条边 x_1\text{-}y_1 和 x_2\text{-}y_2，并假设 x 是 y 的父节点，这会产生以下三种情况：

  1. 删除的两条边在同一颗子树内，且 y_1 是 x_2 的祖先节点（或重合）。

    如下图所示，这三个连通块的异或和分别为 xor}[y_2]、xor}[y_1]\oplus\textit{xor}[y_2] 和 xor}[0]\oplus\textit{xor}[y_1]（\oplus 表示异或运算）。

same.png

  1. 删除的两条边在同一颗子树内，且 y_2 是 x_1 的祖先节点（或重合）。

    同上，这三个连通块的异或和分别为 xor}[y_1]、xor}[y_2]\oplus\textit{xor}[y_1] 和 xor}[0]\oplus\textit{xor}[y_2]。

  2. 删除的两条边分别属于两颗不相交的子树。

    如下图所示，这三个连通块的异或和分别为 xor}[y_1]、xor}[y_2] 和 xor}[0]\oplus\textit{xor}[y_1]\oplus\textit{xor}[y_2]。

    diff.png

因此关键之处在于判断这两条边的关系，这可以用上文提到的时间戳的性质 O(1) 地判断出来。

代码实现时，由于不知道 edges}[i] 两个点的父子关系，枚举边的写法需要额外的判断。我们可以改为枚举不是根的两个点，删除这两个点及其父节点形成的边，这样代码更简洁，效率也略优于枚举边的写法。

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 为 nums 的长度。
  • 空间复杂度：O(n)。
[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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
        n = len(nums)
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        xor, in_, out, clock = [0] * n, [0] * n, [0] * n, 0
        def dfs(x: int, fa: int) -> None:
            nonlocal clock
            clock += 1
            in_[x] = clock
            xor[x] = nums[x]
            for y in g[x]:
                if y != fa:
                    dfs(y, x)
                    xor[x] ^= xor[y]
            out[x] = clock
        dfs(0, -1)

        ans = inf
        for i in range(2, n):
            for j in range(1, i):
                if in_[i] < in_[j] <= out[i]:  # i 是 j 的祖先节点
                    x, y, z = xor[j], xor[i] ^ xor[j], xor[0] ^ xor[i]
                elif in_[j] < in_[i] <= out[j]:  # j 是 i 的祖先节点
                    x, y, z = xor[i], xor[i] ^ xor[j], xor[0] ^ xor[j]
                else:  # 删除的两条边分别属于两颗不相交的子树
                    x, y, z = xor[i], xor[j], xor[0] ^ xor[i] ^ xor[j]
                ans = min(ans, max(x, y, z) - min(x, y, z))
                # 注：把 min max 拆开，改为下面的注释，可以明显加快速度
                # mn = mx = x
                # if y < mn: mn = y 
                # elif y > mx: mx = y
                # if z < mn: mn = z 
                # elif z > mx: mx = z
                # if mx - mn < ans: ans = mx - mn
                if ans == 0: return 0  # 提前退出
        return ans
[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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    List<Integer>[] g;
    int[] nums, xor, in, out;
    int clock;

    public int minimumScore(int[] nums, int[][] edges) {
        var n = nums.length;
        g = new ArrayList[n];
        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;
        xor = new int[n];
        in = new int[n];
        out = new int[n];
        dfs(0, -1);

        var ans = Integer.MAX_VALUE;
        for (int i = 2, x, y, z; i < n; ++i)
            for (var j = 1; j < i; ++j) {
                if (in[i] < in[j] && in[j] <= out[i]) { // i 是 j 的祖先节点
                    x = xor[j];
                    y = xor[i] ^ x;
                    z = xor[0] ^ xor[i];
                } else if (in[j] < in[i] && in[i] <= out[j]) { // j 是 i 的祖先节点
                    x = xor[i];
                    y = xor[j] ^ x;
                    z = xor[0] ^ xor[j];
                } else { // 删除的两条边分别属于两颗不相交的子树
                    x = xor[i];
                    y = xor[j];
                    z = xor[0] ^ x ^ y;
                }
                ans = Math.min(ans, Math.max(Math.max(x, y), z) - Math.min(Math.min(x, y), z));
                if (ans == 0) return 0; // 提前退出
            }
        return ans;
    }

    void dfs(int x, int fa) {
        in[x] = ++clock;
        xor[x] = nums[x];
        for (var y : g[x])
            if (y != fa) {
                dfs(y, x);
                xor[x] ^= xor[y];
            }
        out[x] = clock;
    }
}
[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
33
34
35
36
class Solution {
public:
    int minimumScore(vector<int> &nums, vector<vector<int>> &edges) {
        int n = nums.size();
        vector<vector<int>> g(n);
        for (auto &e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        int xr[n], in[n], out[n], clock = 0;
        function<void(int, int)> dfs = [&](int x, int fa) {
            in[x] = ++clock;
            xr[x] = nums[x];
            for (int y : g[x])
                if (y != fa) {
                    dfs(y, x);
                    xr[x] ^= xr[y];
                }
            out[x] = clock;
        };
        dfs(0, -1);

        int ans = INT_MAX;
        for (int i = 2, x, y, z; i < n; ++i)
            for (int j = 1; j < i; ++j) {
                if (in[i] < in[j] && in[j] <= out[i]) x = xr[j], y = xr[i] ^ x, z = xr[0] ^ xr[i]; // i 是 j 的祖先节点
                else if (in[j] < in[i] && in[i] <= out[j]) x = xr[i], y = xr[j] ^ x, z = xr[0] ^ xr[j]; // j 是 i 的祖先节点
                else x = xr[i], y = xr[j], z = xr[0] ^ x ^ y; // 删除的两条边分别属于两颗不相交的子树
                ans = min(ans, max(max(x, y), z) - min(min(x, y), z));
                if (ans == 0) return 0; // 提前退出
            }
        return ans;
    }
};
[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
48
49
50
51
func minimumScore(nums []int, edges [][]int) int {
	n := len(nums)
	g := make([][]int, n)
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x)
	}

	xor := make([]int, n)
	in := make([]int, n)
	out := make([]int, n)
	clock := 0
	var dfs func(int, int)
	dfs = func(x, fa int) {
		clock++
		in[x] = clock
		xor[x] = nums[x]
		for _, y := range g[x] {
			if y != fa {
				dfs(y, x)
				xor[x] ^= xor[y]
			}
		}
		out[x] = clock
	}
	dfs(0, -1)
	isAncestor := func(x, y int) bool { return in[x] < in[y] && in[y] <= out[x] }

	ans := math.MaxInt32
	for i := 2; i < n; i++ {
		for j := 1; j < i; j++ {
			var x, y, z int
			if isAncestor(i, j) { // i 是 j 的祖先节点
				x, y, z = xor[j], xor[i]^xor[j], xor[0]^xor[i]
			} else if isAncestor(j, i) { // j 是 i 的祖先节点
				x, y, z = xor[i], xor[i]^xor[j], xor[0]^xor[j]
			} else { // 删除的两条边分别属于两颗不相交的子树
				x, y, z = xor[i], xor[j], xor[0]^xor[i]^xor[j]
			}
			ans = min(ans, max(max(x, y), z)-min(min(x, y), z))
			if ans == 0 {
				return 0 // 提前退出
			}
		}
	}
	return ans
}

func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if a < b { return b }; return a }
 Comments
On this page
2322-从树中删除边的最小分数