Tree and Hamilton Path 2 の解説

ほとんどの辺は行って、戻っての2回行わなければならないが、1本のパスだけは行くだけでよい。

なので、全体のコストとしては

$\sum{Ci * 2} - (選ぶパスのコスト合計)$

となる。

これを最小化すれば良くて、つまりは選ぶパスのコスト合計を最大化すればよい。

これは明らかに木の直径を選んであげればよいので、dijkstraを2回やって木の直径を求めてあげて取得してあげればよい。

fn main() {
    input! {
        n: usize,
        abc: [(Usize1, Usize1, usize); n - 1]
    }
    let mut to = vec![vec![]; n];
    let mut base = 0;
    for &(a, b, c) in abc.iter() {
        to[a].push((b, c));
        to[b].push((a, c));
        base += c * 2;
    }

    let f = |v: usize| {
        let mut heap = BinaryHeap::new();
        heap.push((Reverse(0), v));
        let mut det = vec![false; n];
        let mut dist = vec![usize::MAX; n];
        dist[v] = 0;
        while !heap.is_empty() {
            let (_, v) = heap.pop().unwrap();
            if det[v] {
                continue;
            }
            det[v] = true;
            for &(v2, cost) in to[v].iter() {
                if det[v2] {
                    continue;
                }
                let nc = dist[v] + cost;
                if dist[v2] > nc {
                    dist[v2] = nc;
                    heap.push((Reverse(nc), v2));
                }
            }
        }
        dist
    };
    let ans1 = f(0);
    let v1 = ans1.iter().position_max().unwrap();
    let ans2 = f(v1);
    let &ans = ans2.iter().max().unwrap();

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