Overview

The multiplier \(r_i\) assigned to each edge must be an integer of \(1\) or greater, and its cost is \(w_i \times r_i\).
In conclusion, setting \(r_i = 1\) for all edges is optimal, and the answer is the sum of the weights of all edges, \(\sum w_i\).

Analysis

The key point of this problem is that the condition only imposes an upper bound stating that “the sum of multipliers on a path is at most \(k^2\)”.

On the other hand, since each multiplier \(r_i\) is a positive integer, we must have:

\(r_i \geq 1\)

Furthermore, since each weight \(w_i\) is also a positive integer, to minimize the cost \(w_i \times r_i\), we want to make each \(r_i\) as small as possible.
In other words, choosing the minimum possible value for each edge:

\(r_i = 1\)

is the most optimal choice.

Now, we just need to check if the condition is satisfied when we set \(r_i = 1\) for all edges.

Let \(k\) be the number of edges on the path between any two vertices.
In this case, the sum of the multipliers on the path is:

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

The condition is:

\(k \leq k^2\)

Since \(k \geq 1\), this inequality always holds.

Therefore, setting the multiplier of every edge to \(1\) satisfies the condition.

Furthermore, since we cannot have \(r_i < 1\) for any edge, no cost smaller than this can be achieved.
Thus, the minimum cost is:

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

There is no need to enumerate paths or perform tree DP.
Since there are up to \(O(N^2)\) paths between any two vertices, an approach that directly examines them is unnecessary and impractical under the given constraints.

Algorithm

For the \(N-1\) input edges, we simply sum up their weights \(w_i\).

1. Read \(N\)
2. Read each edge \((u_i, v_i, w_i)\)
3. Add \(w_i\) to the answer
4. Finally, output the total sum

The structure of the tree and the vertex indices \(u_i, v_i\) do not affect the answer.

Complexity

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

In the provided code, the entire input is read and stored at once using split(), so the space complexity is \(O(N)\). If we read the input sequentially, the auxiliary space complexity can be reduced to \(O(1)\).

Implementation Details

The input is in the following format:

N
u_1 v_1 w_1
u_2 v_2 w_2
...

When reading with split(), data[0] will be \(N\), followed by elements in the order of:

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

Therefore, the weights \(w_i\) are located at data[3], data[6], data[9], and so on.
In the code, these are summed up as follows:

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

Since Python’s integer type can handle arbitrarily large values, there is no issue even if the answer becomes large.

Source Code

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)

---

This editorial was generated by gpt-5.5-high.