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