2022-11-28：给定两个数组A和B，比如 A = { 0, 1, 1 } B = { 1, 2, 3 } A[0] = 0

use std::iter::repeat;

fn main() {
    let mut a1 = vec![0, 1, 1];
    let mut b1 = vec![1, 2, 3];
    let n1 = 3;
    println!("ans = {}", min_fuel(&mut a1, &mut b1, n1));

    let mut a2 = vec![1, 1, 1, 9, 9, 9, 9, 7, 8];
    let mut b2 = vec![2, 0, 3, 1, 6, 5, 4, 0, 0];
    let n2 = 9;
    println!("ans = {}", min_fuel(&mut a2, &mut b2, n2));
}

static mut CNT: i32 = 0;

fn min_fuel(a: &mut Vec<i32>, b: &mut Vec<i32>, n: i32) -> i32 {
    // 先建图
    let mut graph: Vec<Vec<i32>> = vec![];
    for _i in 0..=n {
        graph.push(vec![]);
    }
    for i in 0..a.len() {
        graph[a[i] as usize].push(b[i]);
        graph[b[i] as usize].push(a[i]);
    }
    // 建图完毕
    // 根据题目描述，办公室一定是0号点
    // 所有员工一定是往0号点汇聚

    // a 号，dfn[a] == 0 没遍历过！
    // dfn[a] != 0 遍历过！
    let mut dfn: Vec<i32> = repeat(0).take((n + 1) as usize).collect();
    // a为头的树，一共有10个节点
    // size[a] = 0
    // size[a] = 10
    let mut size: Vec<i32> = repeat(0).take((n + 1) as usize).collect();
    // 所有居民要汇总吗？
    // a为头的树，所有的居民是要向a来汇聚
    // cost[a] : 所有的居民要向a来汇聚，总油量的耗费
    let mut cost: Vec<i32> = repeat(0).take((n + 1) as usize).collect();
    unsafe { CNT = 0 };
    dfs(&mut graph, 0, &mut dfn, &mut size, &mut cost);
    return cost[0];
}

// 图 ： graph
// 当前的头，原来的编号，不是dfn序号！ : cur
// 从cur开始，请遍历
// 遍历完成后，请把dfn[cur]填好！size[cur]填好！cost[cur]填好
fn dfs(
    graph: &mut Vec<Vec<i32>>,
    cur: i32,
    dfn: &mut Vec<i32>,
    size: &mut Vec<i32>,
    cost: &mut Vec<i32>,
) {
    unsafe {
        CNT += 1;
    }
    dfn[cur as usize] = unsafe { CNT };
    size[cur as usize] = 1;
    for next in graph[cur as usize].clone().iter() {
        if dfn[*next as usize] == 0 {
            dfs(graph, *next, dfn, size, cost);
            size[cur as usize] += size[*next as usize];
            cost[cur as usize] += cost[*next as usize];
            cost[cur as usize] += (size[*next as usize] + 4) / 5;
        }
    }
}