概要

木において、各辺の乗数 \(r_i\) を条件を満たすように設定したときの、全辺のコストの合計の最小値を求める問題です。一見すると複雑な最適化問題に見えますが、条件を整理すると、実はすべての乗数が \(1\) に一意に定まることが分かります。したがって、求める最小値は単にすべての辺の重み \(w_i\) の総和になります。

考察

重要な気づき：長さ \(1\) のパスに注目する

問題文にある以下の条件に注目します。

木の任意の相異なる \(2\) 頂点の組について、パスに含まれる辺の本数を \(k\) としたとき、 \(r_{e_1} + r_{e_2} + \cdots + r_{e_k} \leq k^2\) が成り立たなければならない。

この条件は「任意の相異なる \(2\) 頂点」について成り立つ必要があります。 そこで、最も単純なケースとして、隣接する \(2\) 頂点を結ぶパス（長さ \(k=1\) のパス）を考えてみましょう。

木の任意の辺 \(i\) について、その辺のみからなるパスの長さは \(k=1\) です。このパスに対して条件を適用すると、以下の式が成り立ちます。 $\(r_i \leq 1^2 = 1\)$

一方で、問題文より乗数 \(r_i\) は正の整数（\(1\) 以上の整数）でなければなりません。すなわち、 $\(r_i \geq 1\)$ です。

これら \(2\) つの不等式を同時に満たす整数 \(r_i\) は、\(r_i = 1\) 以外に存在しません。

すべての \(r_i = 1\) としたときの整合性

すべての辺について \(r_i = 1\) としたとき、長さ \(k\) の任意のパスにおける乗数の総和は、 $\(r_{e_1} + r_{e_2} + \cdots + r_{e_k} = \underbrace{1 + 1 + \cdots + 1}_{k \text{ 個}} = k\)$ となります。

任意の正の整数 \(k \geq 1\) において、 \(k \leq k^2\) は常に成り立ちます。したがって、すべての辺の乗数を \(1\) に設定すれば、長さ \(2\) 以上のパスに対する条件もすべて自動的に満たされることが確認できます。

結論

条件を満たす乗数の設定は \(r_i = 1 \ (1 \leq i \leq N-1)\) の \(1\) 通りしか存在しません。 したがって、全辺のコストの合計の最小値は、単にすべての辺の重みの総和となります。 $\(\sum_{i=1}^{N-1} w_i \times 1 = \sum_{i=1}^{N-1} w_i\)$

アルゴリズム

1. 入力から頂点数 \(N\) と、各辺の情報（\(u_i, v_i, w_i\)）を読み込みます。
2. 頂点間のつながり（隣接リストなど）を構築する必要はありません。各辺の重み \(w_i\) のみを足し合わせます。
3. 計算した総和を出力します。

計算量

• 時間計算量: \(O(N)\) \(N-1\) 本の辺の重みを順に走査して足し合わせるだけなので、線形時間 \(O(N)\) で処理が完了します。
• 空間計算量: \(O(N)\) 入力を保持するために必要なメモリは \(O(N)\) です。入力をストリームとして順に処理すれば \(O(1)\) に抑えることも可能です。

実装のポイント

• オーバーフローへの対策: \(N\) は最大で \(2 \times 10^5\)、重み \(w_i\) は最大で \(10^9\) であるため、答えの最大値は \(2 \times 10^{14}\) 程度になります。Pythonでは自動的に多倍長整数が使われるため意識する必要はありませんが、C++ などの言語を使用する場合は、答えを格納する変数に 64 ビット整数型（long long など）を使用してください。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    ans = 0
    for i in range(N - 1):
        ans += int(input_data[3 * i + 3])
    print(ans)

if __name__ == '__main__':
    solve()

---

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