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