概要

各辺に正の整数の乗数 \(r_i\) を設定し、すべての頂点間パスについて「乗数の和 \(\leq\) パス長の二乗」を満たす必要があります。

実は、各辺の乗数は必ず \(1\) に決まるため、答えは全辺の重みの合計です。

考察

条件は「任意の相異なる \(2\) 頂点の組」に対して成り立つ必要があります。

ここで、ある辺 \(i\) に注目します。
辺 \(i\) は頂点 \(u_i\) と \(v_i\) を直接結んでいます。

木では \(u_i\) から \(v_i\) へのパスはこの辺 \(i\) だけなので、パスに含まれる辺の本数は

\[ k = 1 \]

です。

したがって、条件より

\[ r_i \leq 1^2 = 1 \]

が必要です。

一方で、問題文より \(r_i\) は正の整数なので、

\[ r_i \geq 1 \]

です。

よって、

\[ r_i = 1 \]

でなければなりません。

これはすべての辺について同じなので、すべての辺の乗数は必ず \(1\) になります。

つまり、条件を満たす設定は実質的に

\[ r_1 = r_2 = \cdots = r_{N-1} = 1 \]

しかありません。

このとき、任意の長さ \(k\) のパスについて乗数の和は

\[ 1 + 1 + \cdots + 1 = k \]

です。

\(k \geq 1\) なので、

\[ k \leq k^2 \]

が成り立ち、条件を満たします。

したがって、最小コストは単に

\[ \sum_{i=1}^{N-1} w_i \]

です。

素朴にすべての頂点対のパスを調べようとすると、頂点対が \(O(N^2)\) 個あるため、\(N \leq 2 \times 10^5\) では間に合いません。
しかし、長さ \(1\) のパスだけを考えることで、各辺の乗数が \(1\) に固定されることが分かります。

アルゴリズム

1. \(N\) を読み込む。
2. \(N-1\) 本の辺について、\(u_i, v_i, w_i\) を読み込む。
3. 各辺の乗数は必ず \(1\) なので、答えに \(w_i\) を加算する。
4. 合計を出力する。

計算量

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

実装のポイント

重み \(w_i\) は最大 \(10^9\) で、辺の本数は最大 \(2 \times 10^5 - 1\) です。
合計は \(32\) bit 整数に収まらない可能性があるため、long long を使います。

木の構造そのものを使う必要はないので、隣接リストを作る必要もありません。入力された辺の重みをそのまま足し合わせれば十分です。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    long long ans = 0;
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        ans += w;
    }

    cout << ans << '\n';
    return 0;
}

---

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