概要

木構造の各頂点を \(K\) 種類の色で塗り分けます。2種類以上の色を使うという条件のもとで、隣接する頂点間の「色番号の差 \(\times\) 辺の重み」の合計を最小化する問題です。

考察

この問題を解くための重要な観察として、木の性質とコストの下限値に注目します。

まず、すべての頂点を同じ色で塗ることは禁止されています。すなわち、少なくとも2種類以上の色を使う必要があります。2種類以上の色を使うということは、木の中の少なくとも1つの辺において、両端の頂点の色が異なることを意味します。

隣接する頂点の色が異なる場合、その辺の違和感コストは \(W_i \times |a - b|\) となります。ここで \(a \neq b\) であるため、\(|a - b| \ge 1\) です。したがって、色が異なる辺のコストは最低でも \(W_i \times 1 = W_i\) となります。 全体の違和感コストの合計は、各辺のコストの和であるため、最低でも1つの辺の重み以上になります。すなわち、合計コストは木に存在する辺の重みの最小値 \(\min(W_i)\) 以上になることがわかります。

次に、この下限値 \(\min(W_i)\) を実際に達成できるかを考えます。 木から任意の1辺を選び、その辺を取り除くと、木は2つの部分木に分かれます（木は連結で閉路を持たないため）。重みが最小の辺を選び、その辺で木を2つに分割します。 そして、片方の部分木に属するすべての頂点を「色1」で塗り、もう片方の部分木に属するすべての頂点を「色2」で塗ります。 この塗り方では、分割に用いた辺の両端のみが異なる色（色1と色2）となり、そのコストは \(W_{\min} \times |1 - 2| = W_{\min}\) となります。それ以外の辺はすべて同じ色の頂点同士を結んでいるため、コストは \(0\) になります。 \(K \ge 2\) と保証されているため、この塗り分けは常に可能であり、全体の合計コストはちょうど \(W_{\min}\) となります。

したがって、答えはすべての辺の重み \(W_i\) の最小値となります。

アルゴリズム

1. 入力からすべての辺の重み \(W_i\) を読み取ります。
2. それらの中から最小値を見つけます。
3. 最小値を出力します。

計算量

• 時間計算量: \(O(N)\) （すべての辺の重みを1回ずつ調べるため）
• 空間計算量: \(O(1)\) （入力をすべて保持せずに順次処理、あるいは入力全体をメモリに読み込んでも \(O(N)\) で十分収まる）

実装のポイント

Pythonで大量の入力を高速に処理するため、sys.stdin.buffer.read().split() を用いて入力を一度にすべて読み込み、空白区切りで分割します。 入力データのうち、辺の重み \(W_i\) は各行の3番目の要素にあたります。入力データの先頭は N M K の3つの要素であるため、\(W_i\) はデータリストのインデックス 5, 8, 11, ... に位置しています。これらの値のみを走査して最小値を更新することで、非常に簡潔かつ高速に解を求めることができます。

ソースコード

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    # K = int(data[2]) # 使用しない
    
    min_W = 10**9
    # 各行の3番目の要素が W_i にあたる
    # dataのインデックスは 5, 8, 11, ...
    # 開始インデックスは 5
    for i in range(5, len(data), 3):
        w = int(data[i])
        if w < min_W:
            min_W = w
            
    print(min_W)

if __name__ == "__main__":
    solve()

この解説は or-glm5.2-high によって生成されました。