概要

木構造の地図に色 \(1\) から \(K\) を割り当て、少なくとも \(2\) 種類以上の色を使う条件で、辺ごとのコスト \(W_i \times |a-b|\) の合計を最小化する問題です。

結論として、答えは 辺の重み \(W_i\) の最小値 になります。

考察

まず、すべての区画を同じ色で塗れば、すべての辺で \(|a-b|=0\) となるため、コストは \(0\) になります。

しかし、この問題では \(2\) 種類以上の色を使わなければならない ため、全頂点を同じ色にすることはできません。

ここで重要な性質があります。

木は連結なので、もしすべての辺の両端が同じ色なら、すべての頂点が同じ色になります。
したがって、\(2\) 種類以上の色を使うなら、必ず少なくとも \(1\) 本の辺について、両端の色が異なります。

ある辺 \(i\) の両端の色が異なるなら、色番号は整数なので、

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

です。

そのため、その辺だけで少なくとも

\[ W_i \times 1 = W_i \]

のコストがかかります。

よって、どんな塗り方をしても、コストは少なくとも

\[ \min_i W_i \]

以上になります。

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

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

片方の連結成分を色 \(1\)、もう片方を色 \(2\) で塗ります。

すると、色が異なる辺はちょうど辺 \(e\) だけです。
その辺のコストは

\[ W_e \times |1-2| = W_e \]

です。

ここで \(W_e\) は最小の辺重みなので、合計コストは

\[ \min_i W_i \]

になります。

したがって、答えは単に 最小の辺重み です。

素朴に各頂点の色を考えたり、木 DP をしようとすると、\(K\) が最大 \(10^8\) と非常に大きいため現実的ではありません。
しかし、上の考察により、色の具体的な割り当てを考える必要はなく、辺重みの最小値だけを見ればよいです。

アルゴリズム

1. 入力から \(M\) 本の辺を読む。
2. 各辺の重み \(W_i\) を確認する。
3. その最小値を求める。
4. 最小値を出力する。

答えは

\[ \min_{1 \leq i \leq M} W_i \]

です。

計算量

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

入力全体をリストとして読み込んでいるため、実装上の空間計算量は \(O(M)\) です。
ただし、辺を逐次読み込む実装にすれば追加の空間は \(O(1)\) にできます。

実装のポイント

この実装では、入力全体を整数列として読み込んでいます。

data = list(map(int, sys.stdin.buffer.read().split()))

最初の \(3\) 個は \(N, M, K\) なので、辺情報は data[3] 以降にあります。
各辺は

u v w

の \(3\) 個の整数で表されるため、重みは各辺ごとに idx + 2 の位置にあります。

頂点番号 \(u, v\) や色数 \(K\) は、答えの計算には直接使いません。
必要なのは辺重み \(W_i\) の最小値だけです。

ソースコード

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
m = data[1]

ans = 10**18
idx = 3
for _ in range(m):
    w = data[idx + 2]
    if w < ans:
        ans = w
    idx += 3

print(ans)

---

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