概要

木の各頂点に色番号を割り当て、辺ごとのコスト \(W_i \times |a-b|\) の合計を最小化します。
ただし全頂点を同じ色にすることは禁止されているため、答えは「最小の辺重み」になります。

考察

まず、もし「\(2\) 種類以上の色を使う」という制約がなければ、すべての頂点を同じ色にすれば全ての辺のコストが \(0\) になり、最小値は \(0\) です。

しかし今回は、少なくとも \(2\) 種類の色を使う必要があります。

木は連結なので、異なる色が塗られた頂点が存在するなら、その \(2\) 頂点を結ぶパス上のどこかに、必ず両端の色が異なる辺が存在します。

その辺の重みを \(W\)、両端の色を \(a, b\) とすると、\(a \neq b\) なので

\[ |a-b| \geq 1 \]

です。したがって、その辺だけで少なくとも

\[ W \times |a-b| \geq W \]

のコストがかかります。

よって、どんな塗り方をしても、コストは少なくとも「色が変わる辺の重み」以上になります。特に、全体の最小辺重みを \(\min W_i\) とすると、答えは少なくとも

\[ \min W_i \]

です。

次に、この下限を実際に達成できることを示します。

重みが最小の辺を \(1\) 本選びます。この辺を木から取り除くと、木は \(2\) つの連結成分に分かれます。

• 片方の成分をすべて色 \(1\)
• もう片方の成分をすべて色 \(2\)

で塗ります。

すると、色が異なる辺は取り除いた最小重みの辺ただ \(1\) 本だけです。
その辺のコストは

\[ \min W_i \times |1-2| = \min W_i \]

になります。

他の辺は両端が同じ色なのでコストは \(0\) です。

したがって、合計コストはちょうど

\[ \min W_i \]

となり、これが最小値です。

素朴に全ての色の割り当てを試すと \(K^N\) 通りあり、到底間に合いません。
また、木DPを考えても \(K\) が最大 \(10^8\) と非常に大きいため、色ごとの状態を持つ方法は不可能です。
この問題では、木であることと「少なくとも \(2\) 色使う」という条件から、最小辺重みだけを見れば十分です。

アルゴリズム

1. 答え候補 ans を十分大きい値で初期化する。
2. \(M\) 本の辺を順に読み込む。
3. 各辺の重み \(W_i\) について、ans = min(ans, W_i) と更新する。
4. 最後に ans を出力する。

計算量

• 時間計算量: \(O(M)\)
• 空間計算量: \(O(1)\)

実装のポイント

辺の接続先 \(u_i, v_i\) は答えには直接関係ありません。
必要なのは辺重み \(W_i\) の最小値だけです。

また、\(K\) は \(2\) 以上であることが保証されているため、色 \(1\) と色 \(2\) を使った構成が必ず可能です。
そのため、\(K\) の具体的な値は読み込むだけで、計算には使いません。

ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long K;
    cin >> N >> M >> K;

    long long ans = LLONG_MAX;
    for (int i = 0; i < M; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        ans = min(ans, w);
    }

    cout << ans << '\n';
    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。