网站导航
> 技术文档 > 【LeetCode 2322. 从树中删除边的最小分数】解析

【LeetCode 2322. 从树中删除边的最小分数】解析

网友: 技术文档 2025-07-26 21:04:09

目录

  • LeetCode中国站原文
  • 原始题目
    • 题目描述
    • 示例 1：
    • 提示：
  • 讲解
  • 树的切割艺术：DFS与异或的奇妙交响
    • 第一部分：算法思想 —— 穷举、预处理与关系判断
      • 1. 问题的核心：找到最佳的两刀
      • 2. 异或(XOR)的魔法性质
      • 3. 组件的形成与子树的关系
      • 4. 两刀切下的两种情况
      • 5. 如何判断祖先关系？—— DFS时间戳
    • 第二部分：代码实现 —— 组装完整逻辑
      • 代码精讲

LeetCode中国站原文

https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/

原始题目

题目描述

存在一棵无向连通树，树中有 n 个节点。给你一个整数数组 nums，其中 nums[i] 表示第 i 个节点的值。另给你一个二维数组 edges 表示树的边。

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

  1. 分别计算三个组件中所有节点值的异或和。
  2. 分数 = 最大异或和 - 最小异or和。

返回所有可能的删除方案中，最小的分数。

示例 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 小的删除边方案。

提示：

  • n == nums.length
  • 3 <= n <= 1000
  • 1 < = n u m s [ i ] < = 1 0 8 1 <= nums[i] <= 10^8 1<=nums[i]<=108
  • edges 表示一棵有效的树

讲解

树的切割艺术：DFS与异或的奇妙交响

大家好！今天我们要挑战的是一道硬核的树形题目——LeetCode 2322. 从树中删除边的最小分数。这道题综合了树的遍历、位运算的精妙性质以及对树结构的深刻理解，是一道能让你大脑“燃”起来的好题。

第一部分：算法思想 —— 穷举、预处理与关系判断

1. 问题的核心：找到最佳的两刀

我们的目标是找到两条边，切下去之后，产生的三块区域的“异或极差”最小。

最直接的想法是穷举。我们可以在 n-1 条边中，任选两条不同的边进行删除。总共有 (n-1)*(n-2)/2 种组合，对于 n=1000 来说，大约是50万种，这个数量级是可以接受的。

所以，我们的总体思路是：

遍历每一对可能的删除边组合，对于每一种组合，都计算出对应的分数，然后找到全局的最小值。

现在，问题转化成了：对于任意给定的两条删除边，如何高效地计算出三个组件的异或和？

2. 异或(XOR)的魔法性质

异或运算有一个极其美妙的性质，是解决这道题的钥匙：

  • a ^ a = 0 (任何数和自己异或，结果为0)
  • a ^ 0 = a (任何数和0异或，结果是它自己)
  • a ^ b ^ b = a (一个数连续异或同一个数两次，等于没变)
  • 满足交换律和结合律

这意味着，如果我们知道整棵树的总异或和 totalXor，以及其中两个组件的异或和 xor1 和 xor2，那么第三个组件的异或和 xor3 就可以瞬间算出：
xor3 = totalXor ^ xor1 ^ xor2

这太棒了！我们只需要想办法求出任意两个组件的异或和即可。

3. 组件的形成与子树的关系

当我们删除一条边，比如连接 u 和 v 的边（假设 v 是 u 的子节点），树会分裂成两部分：

  1. 以 v 为根节点的子树。
  2. 剩下的其他所有节点。

如果我们能提前知道以任意节点为根的子树的异或和，那么每次切割后，两个组件的异或和就能立刻得到。

这启发我们，需要进行一次预处理：通过一次树的遍历（深度优先搜索DFS），计算出所有节点的子树异或和。

4. 两刀切下的两种情况

现在，我们考虑删除两条边 (u1, v1) 和 (u2, v2)。这里会出现两种拓扑结构，需要分类讨论：

情况一：两条边没有祖先关系（非嵌套）

这意味着，u2 不在 v1 的子树中，u1 也不在 v2 的子树中。

#mermaid-svg-DDTJcm8GLG0Djjlm {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-DDTJcm8GLG0Djjlm .error-icon{fill:#552222;}#mermaid-svg-DDTJcm8GLG0Djjlm .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-DDTJcm8GLG0Djjlm .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-DDTJcm8GLG0Djjlm .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-DDTJcm8GLG0Djjlm .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-DDTJcm8GLG0Djjlm .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-DDTJcm8GLG0Djjlm .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-DDTJcm8GLG0Djjlm .marker{fill:#333333;stroke:#333333;}#mermaid-svg-DDTJcm8GLG0Djjlm .marker.cross{stroke:#333333;}#mermaid-svg-DDTJcm8GLG0Djjlm svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-DDTJcm8GLG0Djjlm .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-DDTJcm8GLG0Djjlm .cluster-label text{fill:#333;}#mermaid-svg-DDTJcm8GLG0Djjlm .cluster-label span{color:#333;}#mermaid-svg-DDTJcm8GLG0Djjlm .label text,#mermaid-svg-DDTJcm8GLG0Djjlm span{fill:#333;color:#333;}#mermaid-svg-DDTJcm8GLG0Djjlm .node rect,#mermaid-svg-DDTJcm8GLG0Djjlm .node circle,#mermaid-svg-DDTJcm8GLG0Djjlm .node ellipse,#mermaid-svg-DDTJcm8GLG0Djjlm .node polygon,#mermaid-svg-DDTJcm8GLG0Djjlm .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-DDTJcm8GLG0Djjlm .node .label{text-align:center;}#mermaid-svg-DDTJcm8GLG0Djjlm .node.clickable{cursor:pointer;}#mermaid-svg-DDTJcm8GLG0Djjlm .arrowheadPath{fill:#333333;}#mermaid-svg-DDTJcm8GLG0Djjlm .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-DDTJcm8GLG0Djjlm .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-DDTJcm8GLG0Djjlm .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-DDTJcm8GLG0Djjlm .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-DDTJcm8GLG0Djjlm .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-DDTJcm8GLG0Djjlm .cluster text{fill:#333;}#mermaid-svg-DDTJcm8GLG0Djjlm .cluster span{color:#333;}#mermaid-svg-DDTJcm8GLG0Djjlm div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-DDTJcm8GLG0Djjlm :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 删除两条边后 整棵树 组件1
(v1的子树) 组件2
(v2的子树) 组件3
(剩余部分) u1 Root u2 ... ...

此时，三个组件的异或和非常清晰：

  • xor1 = subTreeXor[v1]
  • xor2 = subTreeXor[v2]
  • xor3 = totalXor ^ xor1 ^ xor2

情况二：两条边有祖先关系（嵌套）

这意味着，其中一条边所分离出的子树，包含了另一条边。比如说，u2 在 v1 的子树中。

#mermaid-svg-8MoB17C35z1ezBJu {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-8MoB17C35z1ezBJu .error-icon{fill:#552222;}#mermaid-svg-8MoB17C35z1ezBJu .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-8MoB17C35z1ezBJu .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-8MoB17C35z1ezBJu .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-8MoB17C35z1ezBJu .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-8MoB17C35z1ezBJu .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-8MoB17C35z1ezBJu .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-8MoB17C35z1ezBJu .marker{fill:#333333;stroke:#333333;}#mermaid-svg-8MoB17C35z1ezBJu .marker.cross{stroke:#333333;}#mermaid-svg-8MoB17C35z1ezBJu svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-8MoB17C35z1ezBJu .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-8MoB17C35z1ezBJu .cluster-label text{fill:#333;}#mermaid-svg-8MoB17C35z1ezBJu .cluster-label span{color:#333;}#mermaid-svg-8MoB17C35z1ezBJu .label text,#mermaid-svg-8MoB17C35z1ezBJu span{fill:#333;color:#333;}#mermaid-svg-8MoB17C35z1ezBJu .node rect,#mermaid-svg-8MoB17C35z1ezBJu .node circle,#mermaid-svg-8MoB17C35z1ezBJu .node ellipse,#mermaid-svg-8MoB17C35z1ezBJu .node polygon,#mermaid-svg-8MoB17C35z1ezBJu .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-8MoB17C35z1ezBJu .node .label{text-align:center;}#mermaid-svg-8MoB17C35z1ezBJu .node.clickable{cursor:pointer;}#mermaid-svg-8MoB17C35z1ezBJu .arrowheadPath{fill:#333333;}#mermaid-svg-8MoB17C35z1ezBJu .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-8MoB17C35z1ezBJu .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-8MoB17C35z1ezBJu .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-8MoB17C35z1ezBJu .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-8MoB17C35z1ezBJu .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-8MoB17C35z1ezBJu .cluster text{fill:#333;}#mermaid-svg-8MoB17C35z1ezBJu .cluster span{color:#333;}#mermaid-svg-8MoB17C35z1ezBJu div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-8MoB17C35z1ezBJu :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 删除两条边后 整棵树 组件1
(v2的子树) 组件2
(v1子树 \'减去\' v2子树) 组件3
(剩余部分) u1 Root ... u2 ...

此时，三个组件的异或和是：

  • xor1 = subTreeXor[v2] (最里面的那块)
  • xor2 = subTreeXor[v1] ^ subTreeXor[v2] (中间那一环)
  • xor3 = totalXor ^ subTreeXor[v1] (最外面那块)

5. 如何判断祖先关系？—— DFS时间戳

为了区分这两种情况，我们需要一个高效的工具来判断一个节点是否是另一个节点的祖先。最佳方法就是DFS时间戳。

想象一个全局的“时钟” clock。我们进行一次DFS：

  • 进入一个节点 u 时，记下当前时间，inTime[u] = clock++。
  • 离开一个节点 u （即访问完它所有子孙后），再记下当前时间，outTime[u] = clock++。

这样，一个节点 v 是 u 的后代（在u的子树中），当且仅当 v 的整个访问过程发生在 u 的访问过程中。用时间戳来表达就是：

inTime[u] < inTime[v] 并且 outTime[u] > outTime[v]

这个判断的时间复杂度是 O(1)，非常高效！

第二部分：代码实现 —— 组装完整逻辑

现在，我们将上述所有思想整合成最终的、正确的代码。

import java.util.ArrayList;import java.util.List;class Solution { private List<Integer>[] adj; // 邻接表，存储树的结构 private int[] nums; private int[] subTreeXor; // 存储每个节点的子树异或和 private int[] inTime; // 记录节点进入DFS的时间戳 private int[] outTime; // 记录节点离开DFS的时间戳 private int clock = 0; // 全局计时器 public int minimumScore(int[] nums, int[][] edges) { int n = nums.length; // 初始化所有数据结构 this.nums = nums; this.adj = new ArrayList[n]; this.subTreeXor = new int[n]; this.inTime = new int[n]; this.outTime = new int[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); } // 1. 正确地构建邻接表 for (int[] edge : edges) { adj[edge].add(edge); adj[edge].add(edge); } // 2. DFS预处理，计算子树异或和与时间戳 dfs(0, -1); int minScore = Integer.MAX_VALUE; int totalXor = subTreeXor; // 整棵树的异或和 // 3. 穷举所有可能的两条边删除方案 for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n - 1; j++) { // 获取两条边的端点 int u1 = edges[i], v1 = edges[i]; int u2 = edges[j], v2 = edges[j]; // 确定每条边的(parent, child)方向 if (!isDescendant(u1, v1)) { int temp = u1; u1 = v1; v1 = temp; } if (!isDescendant(u2, v2)) { int temp = u2; u2 = v2; v2 = temp; } int xor1, xor2, xor3; // 4. 判断祖先关系并计算分数 if (isDescendant(v1, v2)) { // 情况二：v2 在 v1 的子树内  xor1 = subTreeXor[v2];  xor2 = subTreeXor[v1] ^ xor1;  xor3 = totalXor ^ subTreeXor[v1]; } else if (isDescendant(v2, v1)) { // 情况二：v1 在 v2 的子树内  xor1 = subTreeXor[v1];  xor2 = subTreeXor[v2] ^ xor1;  xor3 = totalXor ^ subTreeXor[v2]; } else { // 情况一：无祖先关系  xor1 = subTreeXor[v1];  xor2 = subTreeXor[v2];  xor3 = totalXor ^ xor1 ^ xor2; } // 计算当前方案的分数并更新全局最小值 int maxVal = Math.max(xor1, Math.max(xor2, xor3)); int minVal = Math.min(xor1, Math.min(xor2, xor3)); minScore = Math.min(minScore, maxVal - minVal); } } return minScore; } // DFS函数，用于预处理 private void dfs(int u, int parent) { inTime[u] = ++clock; // 记录进入时间 subTreeXor[u] = nums[u]; // 初始化为当前节点的值 for (int v : adj[u]) { if (v == parent) continue; dfs(v, u); subTreeXor[u] ^= subTreeXor[v]; // 累加子节点的子树异或和 } outTime[u] = ++clock; // 记录离开时间 } // 辅助函数，高效判断 v 是否是 u 的后代 private boolean isDescendant(int u, int v) { return inTime[u] < inTime[v] && outTime[u] > outTime[v]; }}

代码精讲

  1. DFS预处理: dfs函数是算法的基石。它采用后序遍历的模式，先递归处理完所有子节点，再用子节点的结果来计算当前节点的信息（subTreeXor）。同时，在进入和离开节点时，用全局 clock 记录时间戳，为后续的祖先判断做好准备。
  2. 边的方向: 输入的edges是无向的，但在我们的DFS模型中，树是有向的（从父到子）。在主循环中，我们利用isDescendant辅助函数，在O(1)时间内确定每条边的正确(parent, child)方向，以便正确地使用subTreeXor数组。
  3. 穷举与计算: 双层for循环遍历了所有边的组合。在循环内部，我们通过isDescendant判断是情况一还是情况二，然后套用相应的公式计算出三个组件的异或和，最后更新全局最小分数。

通过这种“预处理 + 穷举分类”的策略，我们将一个复杂的树切割问题，分解成了几个逻辑清晰、易于实现的子模块，最终优雅地解决了它。

网络标签：

相关问题