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

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

一、问题分析

给定一棵无向树，需删除两条边分割为三个连通分量，每个分量的分数为节点值的异或（XOR），方案分数为“最大异或值 - 最小异或值”。目标是找到所有方案中的最小分数。

二、核心思路

1. 异或的可拆分性：若树总异或为 totalXor，子树异或为 x，则剩余部分异或为 totalXor ^ x。
2. 树形DFS预处理：
   • 计算子树异或和（subXor）：以节点为根的子树所有节点值的异或。
   • 记录时间戳（in/out）：判断节点的祖先关系（u 是 v 的祖先 ⇨ in[u] ≤ in[v] ≤ out[u]）。
3. 枚举边对：
   • 每条边由子节点标识（非根节点），枚举所有边对。
   • 分有祖先关系（边在子树内）和无祖先关系（边在不同分支），推导三分量的异或值。

三、算法步骤详解

1. 初始化与树构建

• 邻接表：将边数组转换为邻接表，方便DFS遍历。
• 总异或计算：遍历 nums，计算整棵树的异或值 totalXor。

2. DFS预处理（核心）

private void dfs(int u, int p, int[] nums) { in[u] = timer++; // 记录进入时间 subXor[u] = nums[u]; // 初始化子树异或为自身值 for (int v : graph[u]) { if (v == p) continue; // 跳过父节点，避免循环 parent[v] = u; // 记录父节点 dfs(v, u, nums); // 递归处理子节点 subXor[u] ^= subXor[v]; // 累加子树异或 } out[u] = timer - 1; // 记录离开时间}

• 时间戳：in[u] 是进入节点 u 的时间，out[u] 是离开时间。子树节点的时间戳必在 [in[u], out[u]] 内，用于判断祖先关系。
• 子树异或：通过后序遍历，子树异或和为自身值异或所有子树的异或和。

3. 祖先关系判断

private boolean isAncestor(int u, int v) { return in[u] <= in[v] && out[u] >= out[v];}

若 u 的时间戳范围包含 v 的时间戳，则 u 是 v 的祖先。

4. 枚举边对，计算分数

遍历所有非根节点对 (u, v)（代表两条边 u-parent[u] 和 v-parent[v]）：

for (int u = 1; u < n; u++) { for (int v = 1; v < n; v++) { if (u == v) continue; int xor1, xor2, xor3; // 情况1：u是v的祖先 if (isAncestor(u, v)) { xor1 = subXor[v]; // v的子树 xor2 = subXor[u] ^ xor1; // u的子树去掉v的子树 xor3 = totalXor ^ subXor[u]; // 剩余部分 } // 情况2：v是u的祖先（对称处理） else if (isAncestor(v, u)) { xor1 = subXor[u]; // u的子树 xor2 = subXor[v] ^ xor1; // v的子树去掉u的子树 xor3 = totalXor ^ subXor[v]; // 剩余部分 } // 情况3：无祖先关系 else { xor1 = subXor[u]; // u的子树 xor2 = subXor[v]; // v的子树 xor3 = totalXor ^ xor1 ^ xor2; // 剩余部分 } // 计算当前方案的分数 int max = Math.max(Math.max(xor1, xor2), xor3); int min = Math.min(Math.min(xor1, xor2), xor3); ans = Math.min(ans, max - min); }}

四、完整代码

import java.util.*;class Solution { private List<Integer>[] graph; private int[] in, out, subXor, parent; private int timer = 0; private int totalXor = 0; public int minimumScore(int[] nums, int[][] edges) { int n = nums.length; // 初始化邻接表 graph = new ArrayList[n]; for (int i = 0; i < n; i++) { graph[i] = new ArrayList<>(); } for (int[] edge : edges) { int a = edge[0], b = edge[1]; graph[a].add(b); graph[b].add(a); } // 计算整个树的异或值 totalXor = 0; for (int num : nums) { totalXor ^= num; } // 初始化数组 in = new int[n]; out = new int[n]; subXor = new int[n]; parent = new int[n]; Arrays.fill(parent, -1); timer = 0; // DFS预处理 dfs(0, -1, nums); int ans = Integer.MAX_VALUE; // 枚举所有非根节点对（代表两条边） for (int u = 1; u < n; u++) { for (int v = 1; v < n; v++) { if (u == v) continue; int xor1, xor2, xor3; if (isAncestor(u, v)) {  xor1 = subXor[v]; // v的子树  xor2 = subXor[u] ^ xor1; // u的子树去掉v的子树  xor3 = totalXor ^ subXor[u]; // 剩余部分 } else if (isAncestor(v, u)) {  xor1 = subXor[u]; // u的子树  xor2 = subXor[v] ^ xor1; // v的子树去掉u的子树  xor3 = totalXor ^ subXor[v]; // 剩余部分 } else {  xor1 = subXor[u]; // u的子树  xor2 = subXor[v]; // v的子树  xor3 = totalXor ^ xor1 ^ xor2; // 剩余部分 } int max = Math.max(Math.max(xor1, xor2), xor3); int min = Math.min(Math.min(xor1, xor2), xor3); ans = Math.min(ans, max - min); } } return ans; } // 判断u是否是v的祖先 private boolean isAncestor(int u, int v) { return in[u] <= in[v] && out[u] >= out[v]; } // DFS：计算子树异或值和时间戳 private void dfs(int u, int p, int[] nums) { in[u] = timer++; subXor[u] = nums[u]; for (int v : graph[u]) { if (v == p) continue; parent[v] = u; dfs(v, u, nums); subXor[u] ^= subXor[v]; } out[u] = timer - 1; }}

五、复杂度分析

• 时间复杂度：O(n²)。DFS预处理 O(n)，枚举边对 O(n²)（n ≤ 1000，可高效运行）。
• 空间复杂度：O(n)。存储邻接表和预处理数组。

六、示例验证

以示例1为例：

• 输入：nums = [1,5,5,4,11]，edges = [[0,1],[1,2],[1,3],[3,4]]。
• DFS预处理：
  • subXor[1] = 5 ^ 5 ^ 4 ^ 11 = 15（节点1、2、3、4）。
  • subXor[2] = 5（节点2），subXor[3] = 4 ^ 11 = 15（节点3、4）。
• 枚举边对：选择 u=1（边 1-0）和 v=2（边 2-1）：
  • 三分量异或：5（节点2）、15^5=10（节点1、3、4）、14^15=1（节点0）。
  • 分数：max(5,10,1) - min(5,10,1) = 10-1=9（符合示例输出）。

七、总结

通过 树形DFS预处理 和 边对枚举，结合异或的可拆分性，高效解决树分割问题。核心在于利用时间戳判断祖先关系，快速推导三分量的异或值，确保算法的正确性与效率。

民生知识普及