概要

各辺に設定する乗数 \(r_i\) は \(1\) 以上の整数で、コストは \(w_i \times r_i\) です。
結論として、すべての辺で \(r_i = 1\) とするのが最適であり、答えは全ての辺の重みの和 \(\sum w_i\) になります。

考察

この問題で重要なのは、条件が「パス上の乗数の和が \(k^2\) 以下」という 上限 だけを与えていることです。

一方で、各乗数 \(r_i\) は正の整数なので、必ず

\(r_i \geq 1\)

です。

また、各重み \(w_i\) も正の整数なので、コスト \(w_i \times r_i\) を小さくするには、各 \(r_i\) をできるだけ小さくしたいです。
つまり、各辺について最小値である

\(r_i = 1\)

を選ぶのが最も有利です。

あとは、すべての辺で \(r_i = 1\) としたときに条件を満たすか確認します。

任意の \(2\) 頂点間のパスに含まれる辺の本数を \(k\) とします。
このとき、パス上の乗数の和は

\(1 + 1 + \cdots + 1 = k\)

です。

条件は

\(k \leq k^2\)

ですが、\(k \geq 1\) なのでこれは必ず成り立ちます。

したがって、すべての辺の乗数を \(1\) にする設定は条件を満たします。

さらに、どの辺についても \(r_i < 1\) にはできないため、これより小さいコストは実現できません。
よって最小コストは

\(\sum_{i=1}^{N-1} w_i\)

です。

パスを列挙したり、木DPをしたりする必要はありません。
任意の \(2\) 頂点間のパスは最大で \(O(N^2)\) 個あるため、それらを直接調べるような方針は不要であり、制約的にも現実的ではありません。

アルゴリズム

入力された \(N-1\) 本の辺について、それぞれの重み \(w_i\) だけを足し合わせます。

1. \(N\) を読み込む
2. 各辺 \((u_i, v_i, w_i)\) を読み込む
3. \(w_i\) を答えに加算する
4. 最後に合計値を出力する

木の構造や頂点番号 \(u_i, v_i\) は答えに影響しません。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

提示コードでは入力全体を split() で一括して保持しているため、空間計算量は \(O(N)\) です。
逐次読み込みにすれば、追加の空間は \(O(1)\) にできます。

実装のポイント

入力は

N
u_1 v_1 w_1
u_2 v_2 w_2
...

という形式です。

split() で読み込むと、data[0] が \(N\)、その後は

u_1, v_1, w_1, u_2, v_2, w_2, ...

の順に並びます。

したがって、重み \(w_i\) は data[3], data[6], data[9], … にあります。
コードでは次の部分でそれらを合計しています。

for i in range(3, len(data), 3):
    ans += int(data[i])

Python の整数型は大きな値も扱えるため、答えが大きくなっても問題ありません。

ソースコード

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
ans = 0
for i in range(3, len(data), 3):
    ans += int(data[i])
print(ans)

---

この解説は gpt-5.5-high によって生成されました。