Summary

We need to assign a positive integer multiplier \(r_i\) to each edge such that for all paths between any two vertices, the inequality “sum of multipliers \(\leq\) square of the path length” holds.

In fact, the multiplier for each edge is uniquely determined to be \(1\), so the answer is simply the sum of the weights of all edges.

Analysis

The condition must hold for “any pair of distinct vertices.”

Now, let us focus on a specific edge \(i\).
Edge \(i\) directly connects vertices \(u_i\) and \(v_i\).

Since the graph is a tree, the path from \(u_i\) to \(v_i\) consists of only this edge \(i\), so the number of edges in the path is

\[ k = 1 \]

Therefore, by the condition, we must have

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

On the other hand, since \(r_i\) must be a positive integer according to the problem statement, we have

\[ r_i \geq 1 \]

Thus, we must have

\[ r_i = 1 \]

Since this applies to all edges, the multiplier for every edge must be \(1\).

In other words, the only valid configuration is essentially

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

In this case, for any path of length \(k\), the sum of the multipliers is

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

Since \(k \geq 1\), the inequality

\[ k \leq k^2 \]

holds, satisfying the condition.

Therefore, the minimum cost is simply

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

Naively checking the paths for all pairs of vertices would take too much time for \(N \leq 2 \times 10^5\) since there are \(O(N^2)\) pairs. However, by considering only paths of length \(1\), we can see that the multiplier of each edge is fixed to \(1\).

Algorithm

1. Read \(N\).
2. Read \(u_i, v_i, w_i\) for the \(N-1\) edges.
3. Since the multiplier of each edge must be \(1\), add \(w_i\) to the answer.
4. Output the total sum.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\)

Implementation Details

The weight \(w_i\) can be up to \(10^9\), and the number of edges is up to \(2 \times 10^5 - 1\). Since the total sum might exceed the range of a 32-bit integer, use a 64-bit integer type (like long long in C++).

There is no need to use the tree structure itself, so you do not even need to build an adjacency list. It is sufficient to simply sum up the weights of the input edges.

Source Code

#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;
}

---

This editorial was generated by gpt-5.5-high.