概要

木構造の地図に色を塗り、隣接区画の色番号の差に重みを掛けたコストの総和を最小化する問題です。「2 種類以上の色を使う」という制約のもとで、答えは最小の重みを持つ辺の重みになります。

考察

まず、コストの定義 \(W_i \times |a - b|\) に注目します。\(W_i \geq 1\) かつ \(|a-b| \geq 0\) なので、各境界のコストは必ず \(0\) 以上です。

もし色の種類数に制約がなければ、すべての区画を同じ色番号で塗ることで、すべての境界で \(|a-b| = 0\) となり、総コストは \(0\) になります。しかし本問題では「2 種類以上の色を使う」という制約があるため、これはできません。

そこで「2 種類以上の色を使いつつ、できるだけ無駄なコストを発生させない」方法を考えます。

重要な観察: グラフは連結（木）なので、もし 2 種類以上の色を使うなら、必ず両端の色番号が異なる境界が少なくとも 1 つ存在します。

なぜなら、もしすべての境界で両端の色が同じなら、連結グラフ全体で色が「伝播」して、すべての区画が同じ色になってしまうからです。これは「2 種類以上の色を使う」に反します。

したがって、色番号が異なる境界が最低 1 本あり、その境界のコストは少なくとも

\[W_i \times |a - b| \geq W_i \times 1 = W_i \geq \min_j W_j\]

となります。他の境界のコストは \(0\) 以上なので、総コストは必ず \(\min_j W_j\) 以上です。

アルゴリズム

下界 \(\min_j W_j\) は実際に達成できます。具体的には次のように塗ります。

1. 最も重みが小さい辺 \(e\) を 1 本選ぶ。
2. 木から辺 \(e\) を取り除くと、木は 2 つの連結成分に分かれる。
3. 片方の成分のすべての区画を色 1、もう片方のすべての区画を色 2 で塗る。

この塗り方では：

• 辺 \(e\) の両端は色 1 と色 2 なので、コストは \(W_e \times |1 - 2| = W_e\)。
• それ以外の境界は、両端が同じ成分に属するため同じ色番号となり、コストは \(0\)。

よって総コストはちょうど \(W_e = \min_j W_j\) になります。\(K \geq 2\) なので色 1 と色 2 は必ず使えます。

以上より、答えは入力された辺の重みの最小値です。

実装としては、木の構造（接続関係）を保持する必要すらなく、辺を読み込みながら重みの最小値を取るだけで済みます。

計算量

• 時間計算量: \(O(M)\)（辺を 1 回ずつ読むだけ）
• 空間計算量: \(O(1)\)（重みの最小値だけ保持すればよい）

実装のポイント

• 重みは \(W_i \leq 10^5\) で答えも単一の辺の重みなので、本来 int でも収まりますが、安全のため long long を使っています。

• 最小値の初期値を LLONG_MAX にしておき、各辺の重みと比較して更新します。

• \(u_i, v_i\) の値自体は答えに不要なので、読み飛ばすだけでよいです（木の構築は不要）。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    long long K;
    scanf("%d %d %lld", &N, &M, &K);
    long long ans = LLONG_MAX;
    for(int i=0;i<M;i++){
        long long u,v,w;
        scanf("%lld %lld %lld", &u, &v, &w);
        ans = min(ans, w);
    }
    printf("%lld\n", ans);
    return 0;
}

---

この解説は claude4.8opus-high によって生成されました。