概要\(N\) 頂点の木があり、各辺に正の整数の乗数を設定して、任意のパス上での乗数の和がパス長の2乗以下になるようにします。全辺のコスト（重み \(\times\) 乗数）の合計を最小化する問題です。

考察

まず、各辺の乗数 \(r_i\) は \(1\) 以上の整数という制約があります。したがって、各辺のコスト \(w_i \times r_i\) は常に \(w_i\) 以上となります。これを全ての辺について足し合わせると、全辺のコストの合計は \(\sum w_i \times r_i \geq \sum w_i \times 1 = \sum w_i\) となり、\(\sum w_i\) が理論上の下限値であることがわかります。

次に、この下限値を達成できるかを考えます。問題文のヒントにもある通り、すべての辺の乗数を \(r_i = 1\) に設定してみます。 任意の相異なる2頂点間のパス長を \(k\) とすると、パス上の乗数の和は \(r_{e_1} + \cdots + r_{e_k} = 1 + \cdots + 1 = k\) となります。 パス上の2頂点は相異なるため、パス長 \(k\) は \(1\) 以上の整数になります。\(k \geq 1\) のとき、不等式 \(k \leq k^2\) は常に成立します。

したがって、すべての辺の乗数を \(1\) に設定することは条件を満たし、このときの全辺のコストの合計はちょうど下限値である \(\sum w_i\) となります。よって、求める最小値は \(\sum w_i\) となります。

アルゴリズム

木の構造や頂点番号を記録する必要はなく、入力として与えられた \(N-1\) 個の辺の重み \(w_i\) をそのまま足し合わせるだけで答えが求まります。

計算量

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

実装のポイント

• 重み \(w_i\) は最大 \(10^9\)、辺の数は最大 \(2 \times 10^5\) であるため、合計値は最大 \(2 \times 10^{14}\) になります。32ビット整数（int 型など）ではオーバーフローするため、64ビット整数（C++なら long long 型、Pythonなら標準の整数型）を用いて計算する必要があります。

  ソースコード

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    long long sum = 0;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        sum += w;
    }
    cout << sum << '\n';
    return 0;
}

---

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