Summary

This problem asks us to set a positive integer multiplier for each edge of a tree to minimize the total cost of all edges while satisfying certain path conditions. In fact, setting the multiplier of all edges to \(1\) is optimal.

Intuition

The key point to solving this problem is to pay attention to the constraints on the multipliers \(r_i\).

According to the problem statement, the multiplier \(r_i\) of each edge must be a “positive integer (an integer greater than or equal to \(1\)).” Also, the weight of each edge \(w_i\) is a “positive integer (an integer greater than or equal to \(1\)).”

Therefore, for any edge \(i\), the following holds: $\( r_i \geq 1 \)\( Multiplying both sides by \)w_i\( (\)>0\(), we get: \)\( w_i \times r_i \geq w_i \)\( Since this holds for all edges, the total cost of all edges \)\sum w_i \times r_i\( is at least \)\sum w_i\(. In other words, the **lower bound of the total cost of all edges is \)\sum w_i$**.

Next, we check whether this lower bound can be achieved (i.e., if setting all \(r_i = 1\) satisfies the conditions). Consider the case where the multipliers of all edges are set to \(r_i = 1\). Let \(k\) be the number of edges in the path between any two vertices. The sum of the multipliers along this path is \(\sum r_{e_i} = k\). Since the condition in the problem is “\(\sum r_{e_i} \leq k^2\)”, we just need \(k \leq k^2\). Since the number of edges in a path \(k\) is an integer greater than or equal to \(1\) (\(k \geq 1\)), \(k \leq k^2\) always holds.

Therefore, setting the multiplier of all edges to \(1\) satisfies the conditions and makes the total cost equal to the minimum possible value, \(\sum w_i\). Regardless of the structure of the tree or the edge indices, the answer can be found simply by summing up all the given weights \(w_i\).

Algorithm

1. Read the number of vertices \(N\) from the input.
2. Read the information of each edge (\(u_i, v_i, w_i\)) over \(N-1\) lines.
3. Calculate the total sum of all \(w_i\).
4. Output the total sum.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\) (Since the input is processed sequentially, there is no need to store the structure of the tree)

Implementation Points

• Since the maximum value of \(w_i\) is \(10^9\) and \(N\) is at most \(2 \times 10^5\), the maximum possible answer is around \(2 \times 10^{14}\). When using statically-typed languages like C++, please use a 64-bit integer type (long long) instead of a 32-bit integer type (int) for the variable holding the total sum. In Python, you do not need to worry about integer overflow.

• Although this problem looks like a complex tree problem at first glance, you do not actually need to build the input graph structure; you can solve it simply by reading and summing up the inputs \(w_i\).

  Source Code

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    ans = 0
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        ans += w
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by or-glm5.2-high.