Hard
题目描述
有一个由 n 个节点组成的无向连通树，节点编号从 0 到 n - 1，共有 n - 1 条边。
给你一个长度为 n 的下标从 0 开始的整数数组 nums，其中 nums[i] 表示第 i 个节点的值。另给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。
移除树中的两条不同的边以形成三个连通分量。对于一对移除的边，定义以下步骤：
- 分别获取三个分量中每个分量内所有节点值的异或值。
- 最大异或值和最小异或值之间的差值就是这一对移除边的分数。
例如，假设三个分量的节点值分别为：[4,5,7]、[1,9] 和 [3,3,3]。三个异或值分别为 4 ^ 5 ^ 7 = 6、1 ^ 9 = 8 和 3 ^ 3 ^ 3 = 3。最大异或值是 8，最小异或值是 3。分数为 8 - 3 = 5。
返回给定树上任意一对边移除的最小分数。
示例 1：
输入：nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
输出：9
示例 2：
输入：nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
输出：0
提示：
- n == nums.length
- 3 <= n <= 1000
- 1 <= nums[i] <= 10^8
- edges.length == n - 1
- edges[i].length == 2
- 0 <= ai, bi < n
- ai != bi
- edges 表示一棵有效的树
解题思路
这道题需要移除两条边将树分成三个连通分量，并使得三个分量的异或值的最大值和最小值之间的差值最小。
解题思路：
枚举第一条边：首先枚举要移除的第一条边，移除后树会分成两个连通分量。
预处理子树异或值：对于每个节点，计算以该节点为根的子树的所有节点值的异或值。这可以通过DFS一次性计算完成。
枚举第二条边：在其中一个连通分量中再移除一条边，将其分成两部分。关键是要确保第二条边在第一条边分割出的某个分量内部。
计算三个分量的异或值：
- 设整棵树的异或值为
total - 移除第一条边后，得到两个分量的异或值
- 移除第二条边后，其中一个分量被进一步分割
- 设整棵树的异或值为
处理分量关系：需要特别注意两条被移除的边之间的位置关系：
- 如果两条边没有包含关系，则三个分量互不相交
- 如果一条边在另一条边分割出的子树内，需要正确计算各分量的异或值
优化策略：
- 使用DFS预处理每个子树的异或值
- 通过parent数组判断节点间的祖先关系
- 枚举所有可能的边对组合，计算对应的分数
时间复杂度为O(n²)，因为需要枚举所有可能的边对。空间复杂度为O(n)，用于存储图结构和子树异或值。
代码实现
class Solution {
public:
int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
int n = nums.size();
vector<vector<int>> graph(n);
// 构建邻接表
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
vector<int> xorVal(n), parent(n);
// DFS计算每个子树的异或值
function<void(int, int)> dfs = [&](int u, int p) {
parent[u] = p;
xorVal[u] = nums[u];
for (int v : graph[u]) {
if (v != p) {
dfs(v, u);
xorVal[u] ^= xorVal[v];
}
}
};
dfs(0, -1);
int total = xorVal[0];
int ans = INT_MAX;
// 枚举第一条边
for (auto& edge1 : edges) {
int u1 = edge1[0], v1 = edge1[1];
if (parent[u1] == v1) swap(u1, v1);
// 移除edge1后，v1子树和剩余部分的异或值
int xor1 = xorVal[v1];
int xor2 = total ^ xor1;
// 枚举第二条边
for (auto& edge2 : edges) {
if (edge1 == edge2) continue;
int u2 = edge2[0], v2 = edge2[1];
if (parent[u2] == v2) swap(u2, v2);
int xor3, newXor1, newXor2;
// 检查edge2是否在v1的子树中
bool inSubtree = false;
int curr = v2;
while (curr != -1 && curr != v1) {
curr = parent[curr];
}
if (curr == v1) inSubtree = true;
if (inSubtree) {
// edge2在v1子树中
xor3 = xorVal[v2];
newXor1 = xor1 ^ xor3;
newXor2 = xor2;
} else {
// edge2不在v1子树中
xor3 = xorVal[v2];
newXor1 = xor1;
newXor2 = xor2 ^ xor3;
}
int maxXor = max({newXor1, newXor2, xor3});
int minXor = min({newXor1, newXor2, xor3});
ans = min(ans, maxXor - minXor);
}
}
return ans;
}
};
class Solution:
def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
n = len(nums)
graph = [[] for _ in range(n)]
# 构建邻接表
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
xor_val = [0] * n
parent = [-1] * n
# DFS计算每个子树的异或值
def dfs(u, p):
parent[u] = p
xor_val[u] = nums[u]
for v in graph[u]:
if v != p:
dfs(v, u)
xor_val[u] ^= xor_val[v]
dfs(0, -1)
total = xor_val[0]
ans = float('inf')
# 枚举第一条边
for edge1 in edges:
u1, v1 = edge1
if parent[u1] == v1:
u1, v1 = v1, u1
# 移除edge1后，v1子树和剩余部分的异或值
xor1 = xor_val[v1]
xor2 = total ^ xor1
# 枚举第二条边
for edge2 in edges:
if edge1 == edge2:
continue
u2, v2 = edge2
if parent[u2] == v2:
u2, v2 = v2, u2
# 检查edge2是否在v1的子树中
in_subtree = False
curr = v2
while curr != -1 and curr != v1:
curr = parent[curr]
if curr == v1:
in_subtree = True
if in_subtree:
# edge2在v1子树中
xor3 = xor_val[v2]
new_xor1 = xor1 ^ xor3
new_xor2 = xor2
else:
# edge2不在v1子树中
xor3 = xor_val[v2]
new_xor1 = xor1
new_xor2 = xor2 ^ xor3
max_xor = max(new_xor1, new_xor2, xor3)
min_xor = min(new_xor1, new_xor2, xor3)
ans = min(ans, max_xor - min_xor)
return ans
public class Solution {
public int MinimumScore(int[] nums, int[][] edges) {
int n = nums.Length;
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
// 构建邻接表
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
int[] xorVal = new int[n];
int[] parent = new int[n];
// DFS计算每个子树的异或值
void Dfs(int u, int p) {
parent[u] = p;
xorVal[u] = nums[u];
foreach (int v in graph[u]) {
if (v != p) {
Dfs(v, u);
xorVal[u] ^= xorVal[v];
}
}
}
Dfs(0, -1);
int total = xorVal[0];
int ans = int.MaxValue;
// 枚举第一条边
for (int i = 0; i < edges.Length; i++) {
var edge1 = edges[i];
int u1 = edge1[0], v1 = edge1[1];
if (parent[u1] == v1) {
(u1, v1) = (v1, u1);
}
// 移除edge1后，v1子树和剩余部分的异或值
int xor1 = xorVal[v1];
int xor2 = total ^ xor1;
// 枚举第二条边
for (int j = 0; j < edges.Length; j++) {
if (i == j) continue;
var edge2 = edges[j];
int u2 = edge2[0], v2 = edge2[1];
if (parent[u2] == v2) {
(u2, v2) = (v2, u2);
}
// 检查edge2是否在v1的子树中
bool inSubtree = false;
int curr = v2;
while (curr != -1 && curr != v1) {
curr = parent[curr];
}
if (curr == v1) inSubtree = true;
int xor3, newXor1, newXor2;
if (inSubtree) {
// edge2在v1子树中
xor3 = xorVal[v2];
newXor1 = xor1 ^ xor3;
newXor2 = xor2;
} else {
// edge2不在v1子树中
xor3 = xorVal[v2];
newXor1 = xor1;
newXor2 = xor2 ^ xor3;
}
int maxXor = Math.Max(Math.Max(newXor1, newXor2), xor3);
int minXor = Math.Min(Math.Min(newXor1, newXor2), xor3);
ans = Math.Min(ans, maxXor - minXor);
}
}
return ans;
}
}
var minimumScore = function(nums, edges) {
const n = nums.length;
const graph = Array.from({length: n}, () => []);
// 构建邻接表
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const xorVal = new Array(n).fill(0);
const parent = new Array(n).fill(-1);
// DFS计算每个子树的异或值
function dfs(u, p) {
parent[u] = p;
xorVal[u] = nums[u];
for (const v of graph[u]) {
if (v !== p) {
dfs(v, u);
xorVal[u] ^= xorVal[v];
}
}
}
dfs(0, -1);
const total = xorVal[0];
let ans = Infinity;
// 枚举第一条边
for (let i = 0; i < edges.length; i++) {
const edge1 = edges[i];
let [u1, v1] = edge1;
if (parent[u1]
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |