概要

この問題は、木構造のグラフにおいて、隣接する頂点に塗られた色番号の差に辺の重みを掛けた「違和感コスト」の合計を最小化する問題です。ただし、「2種類以上の色を使わなければならない」という制約があります。

一見すると動的計画法（DP）などを使う複雑な問題に見えますが、木の性質を上手く利用することで、「すべての辺の重み \(W_i\) のうちの最小値」がそのまま答えになるという、非常にシンプルな問題に帰着できます。

---

考察

1. 制約がない場合

もし「2種類以上の色を使う」という制約がなければ、すべての区画に同じ色（例えば色 \(1\)）を塗ればよいです。 このとき、すべての隣接する区画の色番号の差は \(|1 - 1| = 0\) となり、違和感コストの合計は \(0\)（最小）になります。

2. 「2種類以上の色を使う」という制約の影響

しかし、問題文には「2種類以上の色を使わなければならない」という制約があります。 すべての区画に同じ色を塗ることは許されないため、少なくとも1つの辺において、その両端の区画に異なる色を塗る必要があります。

隣接する区画 \(u, v\) の色が異なる（\(a \neq b\)）とき、色番号は整数なので、その差の絶対値は最低でも \(1\) になります（\(|a - b| \geq 1\)）。 したがって、この辺における違和感コストは、最低でも \(W_i \times 1 = W_i\) かかることになります。

3. 木の性質を利用した最適な塗り分け

コストをできるだけ小さくするためには、「色が異なる辺」をちょうど1つだけに抑え、その両端の色番号の差を最小の \(1\) にするのが最適です。

木構造には、「任意の1本の辺を取り除くと、グラフがちょうど2つの連結成分（部分木）に分かれる」という重要な性質があります。

これを利用して、以下のような塗り分けを行います： 1. 任意の1本の辺 \(e = (u, v)\) を選ぶ。 2. この辺 \(e\) を取り除いたときに分かれる2つのグループを、グループA、グループBとする。 3. グループAのすべての区画に色 \(c\) を塗る。 4. グループBのすべての区画に色 \(c+1\) を塗る。

この塗り分けを行うと、各辺のコストは以下のようになります： - グループAの内部を結ぶ辺：両端とも色 \(c\) なので、コストは \(0\) - グループBの内部を結ぶ辺：両端とも色 \(c+1\) なので、コストは \(0\) - グループAとグループBを結ぶ唯一の辺（選んだ辺 \(e\)）：両端の色が \(c\) と \(c+1\) なので、コストは \(W_e \times |c - (c+1)| = W_e\)

このとき、使っている色は \(c\) と \(c+1\) の2種類なので、問題の制約を満たしています。そして、全体の違和感コストの合計は \(W_e\) だけになります。

4. 具体例での確認

例えば、以下のような3つの区画が1列に並んだ木（パス）を考えます。

[区画1] -- (重み 5) -- [区画2] -- (重み 3) -- [区画3]

• 重み 3 の辺を境界にする場合： 区画1と2に色 \(1\)、区画3に色 \(2\) を塗ります。

  • 辺(1, 2)のコスト: \(5 \times |1 - 1| = 0\)
  • 辺(2, 3)のコスト: \(3 \times |1 - 2| = 3\)
  • 合計コスト: \(3\)

• 重み 5 の辺を境界にする場合： 区画1に色 \(1\)、区画2と3に色 \(2\) を塗ります。

  • 辺(1, 2)のコスト: \(5 \times |1 - 2| = 5\)
  • 辺(2, 3)のコスト: \(3 \times |2 - 2| = 0\)
  • 合計コスト: \(5\)

コストを最小化するためには、選ぶ辺 \(e\) の重み \(W_e\) が最小であるものを選べばよいことが分かります。 したがって、求める最小コストは、すべての辺の重み \(W_i\) の最小値となります。

---

アルゴリズム

1. 入力から辺の数 \(M\) と、各辺の重み \(W_i\) を読み込みます。
2. \(W_1, W_2, \ldots, W_M\) の中から最小値を求めます。
3. その最小値を出力します。

頂点の情報（どの頂点とどの頂点が結ばれているか）は、答えに影響しないため無視して構いません。

---

計算量

• 時間計算量: \(O(M)\) すべての辺の重みを1回ずつ確認するだけでよいため、辺の数 \(M\) に対する線形時間で動作します。\(M = N - 1 \le 2 \times 10^5\) であるため、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(1)\) 入力を順番に読み込みながら最小値を更新すればよいため、グラフ全体をメモリに保持する必要はなく、余分なメモリはほぼ使いません。

---

実装のポイント

• Pythonで大量の入力を処理する場合、sys.stdin.read().split() を使うことで、高速に入力を読み込むことができます。

• 頂点 \(u_i, v_i\) の情報は最小値の計算に使わないため、読み飛ばして重み \(W_i\) だけを抽出して処理しています。

  ソースコード

import sys

def solve():
    # 高速な入出力
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # 各辺の重み W_i の最小値を求める
    min_w = float('inf')
    for i in range(M):
        w = int(input_data[3 + i * 3 + 2])
        if w < min_w:
            min_w = w
            
    print(min_w)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-high によって生成されました。