Overview

There is a tree with \(N\) vertices. We assign a positive integer multiplier to each edge such that the sum of the multipliers on any path is at most the square of the path length. The problem asks to minimize the total cost of all edges (weight \(\times\) multiplier).

Analysis

First, there is a constraint that the multiplier \(r_i\) for each edge must be an integer of \(1\) or greater. Therefore, the cost of each edge \(w_i \times r_i\) is always at least \(w_i\). Summing this over all edges, the total cost of all edges is \(\sum w_i \times r_i \geq \sum w_i \times 1 = \sum w_i\), which shows that \(\sum w_i\) is the theoretical lower bound.

Next, let’s consider whether this lower bound can be achieved. As suggested by the hint in the problem description, let’s try setting the multiplier of all edges to \(r_i = 1\). Let \(k\) be the length of the path between any two distinct vertices. The sum of the multipliers on this path is \(r_{e_1} + \cdots + r_{e_k} = 1 + \cdots + 1 = k\). Since the two vertices on the path are distinct, the path length \(k\) is an integer of \(1\) or greater. When \(k \geq 1\), the inequality \(k \leq k^2\) always holds.

Therefore, setting the multipliers of all edges to \(1\) satisfies the condition, and the total cost of all edges in this case is exactly the lower bound \(\sum w_i\). Thus, the minimum value we seek is \(\sum w_i\).

Algorithm

There is no need to record the tree structure or the vertex indices. The answer can be found simply by summing up the weights \(w_i\) of the \(N-1\) edges given in the input.

Complexity

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

Implementation Details

• Since the weight \(w_i\) can be up to \(10^9\) and the number of edges is up to \(2 \times 10^5\), the total sum can be up to \(2 \times 10^{14}\). This will overflow a 32-bit integer (such as the int type), so it is necessary to perform the calculation using a 64-bit integer (long long in C++, or the standard integer type in Python).

  Source Code

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

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