概要

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

考察

まず、コストは各境界で \(W_i \times |a - b|\) と定義されます。もし条件がなければ、すべての区画を同じ色番号にすることですべての境界で \(|a-b| = 0\) となり、コストは \(0\) で済みます。しかし本問では「2 種類以上の色を使う」という制約があるため、これは許されません。

ここで重要な観察をします。

観察 1: 少なくとも 1 つの境界で色番号が異なる

グラフは連結で、2 種類以上の色を使うので、異なる色が塗られた区画のペアが必ず存在します。その 2 区画を結ぶパスのどこかで必ず色番号が切り替わるため、両端の色番号が異なる境界が少なくとも 1 つ存在します。その境界のコストは $\(W_i \times |a - b| \geq W_i \times 1 \geq (\text{重みの最小値})\)\( となります（色番号は整数なので、異なるなら差は最低でも \)1$）。

したがって、総コストは必ず「重みの最小値」以上になります。

観察 2: 重みの最小値はちょうど達成できる

木では、任意の 1 本の辺を取り除くと、グラフはちょうど 2 つの連結成分に分かれます。そこで、重みが最小の辺 \(e\) を選び、\(e\) で分割される一方の成分をすべて色 \(1\)、もう一方をすべて色 \(2\) で塗ります。

すると、 - 辺 \(e\) の境界だけが色番号の異なる区画をつなぎ、コストは \(W_e \times |1 - 2| = W_e\) - それ以外の境界は同じ成分内にあり、両端とも同じ色番号なのでコスト \(0\)

となり、総コストはちょうど \(W_e\)（＝重みの最小値）になります。

観察 1 と観察 2 を合わせると、答えは辺の重みの最小値であることがわかります。

アルゴリズム

実は木の構造そのものは答えに影響せず、入力中のすべての辺の重み \(W_i\) の最小値を求めるだけで答えになります。

入力を読みながら \(W_i\) の最小値を更新していくだけで解けます。グラフを構築したり探索したりする必要はありません。

計算量

• 時間計算量: \(O(N)\)（辺の数 \(M = N - 1\) を 1 回ずつ走査するだけ）
• 空間計算量: \(O(1)\)（最小値を保持する変数のみ。入力読み込み分を除く）

実装のポイント

• \(u_i, v_i\) は答えに不要なので読み飛ばしてよく、\(W_i\) の最小値だけを管理すれば十分です。

• \(N\) が最大 \(2 \times 10^5\) と大きいため、入力の読み込みは高速に行うのが安全です。コードでは sys.stdin.buffer.read() で一括読み込みし、トークンごとに処理しています。

• 色数 \(K \geq 2\) と区画数 \(N \geq 2\) が保証されているため、条件を満たす塗り方は必ず存在し、答えは常に存在します（特別な例外処理は不要です）。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    k = int(data[idx]); idx += 1
    ans = None
    for _ in range(m):
        # u, v, w
        idx += 2  # skip u, v
        w = int(data[idx]); idx += 1
        if ans is None or w < ans:
            ans = w
    print(ans)

main()

---

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