Submission #66576296

---

Source Code Expand

use proconio::input;

fn main() {
    input! {
        n: usize,
        mut x: [i32; n],
        v: [(usize, usize, i32); n - 1]
    }

    let mut edges = vec![Vec::new(); n];
    for (u, v, w) in v {
        let u = u - 1;
        let v = v - 1;
        edges[u].push((v, w));
        edges[v].push((u, w));
    }

    let mut ans = 0;
    loop {
        let mut flag = true;

        for node in 0..n {
            if edges[node].len() == 1 {
                let (next, we) = edges[node][0];
                edges[node].clear();
                let (i, _) = edges[next].iter().enumerate().filter(|(_, &(k, _))| k == node).next().unwrap();
                edges[next].remove(i);
                ans += we * x[node].abs();
                x[next] += x[node];
                x[node] = 0;
                flag = false;
            }
        }

        if flag {
            break;
        }
    }

    println!("{}", ans);
}

Submission Info

Judge Result