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];
}
}
}
评论