概要

木の各辺に正の整数の乗数を設定し、特定のパスの条件を満たしつつ全辺のコストの合計を最小化する問題です。実は、すべての辺の乗数を \(1\) に設定したときが最適になります。

考察

この問題を解くための重要なポイントは、乗数 \(r_i\) の制約に注目することです。

問題文より、各辺の乗数 \(r_i\) は「正の整数（\(1\) 以上の整数）」でなければなりません。また、辺の重み \(w_i\) も「正の整数（\(1\) 以上の整数）」です。

したがって、任意の辺 \(i\) について以下のことが成り立ちます。 $\( r_i \geq 1 \)\( 両辺に \)w_i\(（\)>0\(）を掛けると、 \)\( w_i \times r_i \geq w_i \)\( となります。すべての辺についてこれが成り立つため、全辺のコストの合計 \)\sum w_i \times r_i\( は、少なくとも \)\sum w_i\( 以上になることがわかります。つまり、全辺のコストの合計の**下限は \)\sum w_i$** です。

次に、この下限を達成できるか（すなわち、すべての \(r_i = 1\) が条件を満たすか）を確認します。 すべての辺の乗数を \(r_i = 1\) に設定した場合を考えます。任意の2頂点間のパスに含まれる辺の本数を \(k\) とすると、そのパス上の乗数の合計は \(\sum r_{e_i} = k\) となります。 問題の条件は「\(\sum r_{e_i} \leq k^2\)」なので、\(k \leq k^2\) となればよいです。 パスの辺の本数 \(k\) は \(1\) 以上の整数（\(k \geq 1\)）であるため、常に \(k \leq k^2\) が成り立ちます。

したがって、すべての辺の乗数を \(1\) に設定すれば条件を満たし、かつコストの合計が最小値 \(\sum w_i\) に等しくなります。木の形状や辺の番号は一切関係なく、与えられた重み \(w_i\) をすべて足し合わせるだけで答えが求まります。

アルゴリズム

1. 入力から頂点数 \(N\) を読み込む。
2. \(N-1\) 行にわたって、各辺の情報（\(u_i, v_i, w_i\)）を読み込む。
3. すべての \(w_i\) の合計値を計算する。
4. 合計値を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力を順次処理するため、木の構造を保持する必要がありません）

実装のポイント

• \(w_i\) の最大値が \(10^9\)、\(N\) が最大 \(2 \times 10^5\) であるため、答えの最大値は \(2 \times 10^{14}\) 程度になります。C++などの静的型付け言語を使用する場合は、32ビット整数型（int）ではなく64ビット整数型（long long）を合計値の変数に使用してください。Pythonでは整数型のオーバーフローを気にする必要はありません。

• この問題は一見複雑な木の問題に見えますが、入力のグラフ構造を実際に構築する必要はなく、単に \(w_i\) の入力を受け取って足すだけで解くことができます。

  ソースコード

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    ans = 0
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        ans += w
    print(ans)

if __name__ == '__main__':
    solve()

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