2022-09-27：给定一个棵树，
树上每个节点都有自己的值，记录在数组nums里，
比如nums4 = 10，表示4号点的值是10，
给定树上的每一条边，记录在二维数组edges里，
比如edges8 = {4, 9}表示4和9之间有一条无向边，
可以保证输入一定是一棵树，只不过边是无向边，
那么我们知道，断掉任意两条边，都可以把整棵树分成3个部分。
假设是三个部分为a、b、c，
a部分的值是：a部分所有点的值异或起来，
b部分的值是：b部分所有点的值异或起来，
c部分的值是：c部分所有点的值异或起来，
请问怎么分割，能让最终的：三个部分中最大的异或值 - 三个部分中最小的异或值，最小。
返回这个最小的差值。
输入：nums = 1,5,5,4,11, edges = [0,1,1,2,1,3,3,4]。
输出：9。
答案2022-09-27：
dfn序号。
这道题来自力扣2322。力扣上测试了好几种语言的代码，go语言运行效率是最高，其次是java；rust表现不佳，原因是代码中有复制切片的行为。内存占用go是最低的，rust偏高，原因是代码中有复制切片的行为。
时间复杂度：O(n^2)。
空间复杂度：O(n)。
代码用rust编写。代码如下：
代码语言：rust复制use std::iter::repeat;
fn main() {
let mut nums = vec![1, 5, 5, 4, 11];
let mut edges = vec![vec![0, 1], vec![1, 2], vec![1, 3], vec![3, 4]];
let ans = minimum_score(&mut nums, &mut edges);
println!("ans = {}", ans);
}
const MAX_VALUE: i32 = 1 << 31 - 1;
static mut cnt: i32 = 0;
fn minimum_score(nums: &mut Vec<i32>, edges: &mut Vec<Vec<i32>>) -> i32 {
let n = nums.len() as i32;
// 先建立图
// ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
let mut graph: Vec<Vec<i32>> = vec![];
// 4个点，0、1、2、3
// 0 : {}
// 1 : {}
// 2 : {}
// 3 : {}
for _i in 0..n {
graph.push(vec![]);
}
for edge in edges.iter() {
// a,b
// graph.get(a).add(b);
// graph.get(b).add(a);
graph[edge[0] as usize].push(edge[1]);
graph[edge[1] as usize].push(edge[0]);
}
// 无向边组成的无环图
// 为了方便，就认为0是头
// dfn[i] = ?
let mut dfn: Vec<i32> = repeat(0).take(n as usize).collect();
// xor[i] 以i为头的整棵树，整体异或的结果是多少？
let mut xor: Vec<i32> = repeat(0).take(n as usize).collect();
// size[i] 以i为头的整棵树，一共几个点？
let mut size: Vec<i32> = repeat(0).take(n as usize).collect();
unsafe {
cnt = 1;
}
dfs(nums, &mut graph, 0, &mut dfn, &mut xor, &mut size);
let mut ans = MAX_VALUE;
let m = edges.len() as i32;
let mut cut1: i32;
let mut cut2: i32;
let mut pre: i32;
let mut pos: i32;
let mut part1: i32;
let mut part2: i32;
let mut part3: i32;
let mut max: i32;
let mut min: i32;
for i in 0..m {
// i，要删掉的第一条边，i号边
// edges[i][0] edges[i][1] dfn 谁大，谁就是删掉之后的树的头！cut1
// a b cut1
// { a, b}
// 0 1
let a = edges[i as usize][0];
let b = edges[i as usize][1];
cut1 = if dfn[a as usize] < dfn[b as usize] {
b
} else {
a
};
for j in (i 1)..m {
// j, 要删掉的第二条边，j号边
// { c, d}
// 0 1
let c = edges[j as usize][0];
let d = edges[j as usize][1];
cut2 = if dfn[c as usize] < dfn[d as usize] {
d
} else {
c
};
// cut1，cut2
pre = if dfn[cut1 as usize] < dfn[cut2 as usize] {
cut1
} else {
cut2
};
pos = if pre == cut1 { cut2 } else { cut1 };
// 早 pre 晚 pos
part1 = xor[pos as usize];
// pos为头的树，是pre为头的树的子树！
if dfn[pos as usize] < dfn[pre as usize] size[pre as usize] {
part2 = xor[pre as usize] ^ xor[pos as usize];
part3 = xor[0] ^ xor[pre as usize];
} else {
// pos为头的树，不是pre为头的树的子树！
part2 = xor[pre as usize];
part3 = xor[0] ^ part1 ^ part2;
}
max = get_max(get_max(part1, part2), part3);
min = get_min(get_min(part1, part2), part3);
ans = get_min(ans, max - min);
}
}
return ans;
}
fn get_max<T: Clone Copy std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
fn get_min<T: Clone Copy std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
// 所有节点的值，存在nums数组里
// 整个图结构，存在graph里
// 当前来到的是cur号点
// 请把cur为头，整棵树，所有节点的dfn、size、xor填好！
// 返回！
fn dfs(
nums: &mut Vec<i32>,
graph: &mut Vec<Vec<i32>>,
cur: i32,
dfn: &mut Vec<i32>,
xor: &mut Vec<i32>,
size: &mut Vec<i32>,
) {
// 当前节点了！，
dfn[cur as usize] = unsafe { cnt };
unsafe {
cnt = 1;
}
// 只是来到了cur的头部！
xor[cur as usize] = nums[cur as usize];
size[cur as usize] = 1;
// 遍历所有的孩子！
for next in graph.clone()[cur as usize].iter() {
//有clone，会影响性能
// 只有dfn是0的孩子，才是cur在树中的下级！！！！
if dfn[*next as usize] == 0 {
// cur某个孩子是next
dfs(nums, graph, *next, dfn, xor, size);
// next整棵树的异或和，
xor[cur as usize] ^= xor[*next as usize];
// next整棵树的size
size[cur as usize] = size[*next as usize];
}
}
}执行结果如下：
在这里插入图片描述
在这里插入图片描述左神java代码
