なんだか体調が悪い。また一段と寒くなったからだろうか。鼻水が出る……。

ABC214 : AtCoder Beginner Contest 214

• D - Sum of Maximum Weights https://atcoder.jp/contests/abc214/tasks/abc214_d
  • 提出: https://atcoder.jp/contests/abc214/submissions/47382929
  • 解説 AC
  • 解説を読んでしまうと納得だし D 問題の難易度だと思うけど、思いつかなかった
  • ある辺が答えに加算されるのは両端の頂点から伸びる辺がすべてその辺の重み以下であるとき
  • なので辺を重みの昇順に並べて両端の連結成分のサイズを掛けながら計算していけば良い

use ac_library::Dsu;
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        mut uvw: [(Usize1, Usize1, usize); n - 1],
    };
    uvw.sort_by_key(|&(_, _, w)| w);
    let mut sum = 0_usize;
    let mut dsu = Dsu::new(n);
    for (u, v, w) in uvw {
        sum += dsu.size(u) * dsu.size(v) * w;
        dsu.merge(u, v);
    }
    let ans = sum;
    println!("{}", ans);
}

今日のコミット。

• kireta 1 commit
  • Fix error handling
• rust-atcoder 1 commit
  • abc214 d