Overview

This problem asks us to color a tree-structured map with at least \(2\) different colors to minimize the total discomfort cost between adjacent regions.

Analysis

First, the total discomfort cost is calculated as the sum of \(W_i \times |a - b|\). If there were no constraint requiring us to use “at least \(2\) different colors”, we could color all regions with the same color, making the total discomfort cost \(0\).

However, this time we must use at least \(2\) different colors. This means we must change colors at least once. To minimize the discomfort cost, we should “minimize the number of places where colors change, and minimize the difference between the color IDs”.

Since the map is a tree, cutting a single edge splits it into two subtrees. Thus, we can choose an edge \((u, v)\), color all vertices in the subtree containing \(u\) with color \(1\), and color all vertices in the subtree containing \(v\) with color \(2\). Since both color \(1\) and color \(2\) are used, this satisfies the condition of using at least \(2\) colors.

In this coloring, the color only changes across the chosen edge \((u, v)\). For all other edges, both endpoints have the same color, so their discomfort cost is \(0\). The cost of the chosen edge \((u, v)\) is \(W_i \times |1 - 2| = W_i \times 1 = W_i\).

Therefore, the total discomfort cost is exactly the weight \(W_i\) of the chosen edge. To minimize this, we just need to choose the edge with the minimum weight \(W\) among all edges.

Algorithm

We find the minimum value among the weights \(W_i\) of the \(M\) edges given in the input and output it. The information about adjacent regions (\(u_i, v_i\)) and the number of colors \(K\) are not directly used in the process of finding the minimum value.

Complexity

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

Implementation Points

• It is safe to read the weights \(W\) using a long long type.

• When searching for the minimum value, initialize it with a sufficiently large value (for example, std::numeric_limits<long long>::max()).

  Source Code

#include <iostream>
#include <algorithm>
#include <limits>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    long long K;
    cin >> N >> M >> K;
    long long min_w = numeric_limits<long long>::max();
    for (int i = 0; i < M; ++i) {
        int u, v;
        long long W;
        cin >> u >> v >> W;
        if (W < min_w) {
            min_w = W;
        }
    }
    cout << min_w << endl;
    return 0;
}

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