豆包 LeetCode 2322.从树中删除边的最小分数 public int minimumScore(int[] nums, int[][] edges)

LeetCode 2322 从树中删除边的最小分数题意给一棵无向树节点值为 nums[] 删掉两条不同边把树分成三棵连通子树。定义分数 三棵子树异或和的最大值 - 最小值求最小分数。核心思路1. 整树总异或 totalXor2. 树形DFS预处理每个子树的异或值 父子从属关系3. 枚举删两条边- 情况1两条边祖孙关系分出 a, b, total^a- 情况2两条边互不相交分出 a, b, total^a^b4. 对每种三元组求 max-min 取全局最小Java 完整AC代码javaimport java.util.*;class Solution {ListInteger[] g;int[] xor;int[] nums;int total;boolean[][] isChild;int n;public int minimumScore(int[] nums, int[][] edges) {this.nums nums;n nums.length;g new ArrayList[n];for (int i 0; i n; i) g[i] new ArrayList();for (int[] e : edges) {g[e[0]].add(e[1]);g[e[1]].add(e[0]);}xor new int[n];isChild new boolean[n][n];dfs(0, -1);total xor[0];int res Integer.MAX_VALUE;// 枚举两条要切掉的子树根节点 u, vfor (int u 1; u n; u) {for (int v u 1; v n; v) {int a xor[u], b xor[v];int x, y, z;if (isChild[u][v]) {// v在u子树里x b;y a ^ b;z total ^ a;} else if (isChild[v][u]) {// u在v子树里x a;y b ^ a;z total ^ b;} else {// 互不包含x a;y b;z total ^ a ^ b;}int max Math.max(Math.max(x, y), z);int min Math.min(Math.min(x, y), z);res Math.min(res, max - min);}}return res;}void dfs(int u, int fa) {xor[u] nums[u];for (int v : g[u]) {if (v fa) continue;dfs(v, u);xor[u] ^ xor[v];// 标记所有后代for (int i 0; i n; i) {if (isChild[v][i]) isChild[u][i] true;}isChild[u][v] true;}}}关键解释1. dfs 作用- 算出每个节点为根的子树异或和 xor[u]- isChild[i][j] j 是否在 i 的子树内2. 删两条边等价树删边 切掉一棵子树枚举所有两个子树即可。3. 三种分割异或- 嵌套 b 、 a^b 、 total^a- 并列 a 、 b 、 total^a^b4. 复杂度- 预处理O(n^2)- 枚举两两边O(n^2)题目数据范围可稳过。精简考点- 树上子树异或经典套路- 分割树三部分异或分类讨论- 快速判断子树包含关系需要我给你Python / C / Go 同逻辑版本或者手写一步步推演样例吗