Overview

This problem asks us to minimize the total “discomfort cost” in a tree graph, where the cost is the sum of the edge weights multiplied by the absolute difference between the color numbers painted on adjacent vertices. However, there is a constraint that “at least two different colors must be used.”

At first glance, this might look like a complex problem requiring Dynamic Programming (DP) or similar techniques. However, by leveraging the properties of a tree, it reduces to an extremely simple problem where “the minimum value among all edge weights \(W_i\)” is the answer itself.

---

Analysis

1. Without Constraints

If there were no constraint to use at least two colors, we could simply paint all vertices with the same color (for example, color \(1\)). In this case, the difference between the color numbers of all adjacent vertices would be \(|1 - 1| = 0\), and the total discomfort cost would be \(0\) (the absolute minimum).

2. Impact of the “At Least Two Colors Must Be Used” Constraint

However, the problem statement specifies that “at least two different colors must be used.” Since we are not allowed to paint all vertices with the same color, we must paint the vertices at the endpoints of at least one edge with different colors.

When adjacent vertices \(u, v\) have different colors (\(a \neq b\)), since the color numbers are integers, the absolute difference between them is at least \(1\) (\(|a - b| \geq 1\)). Therefore, the discomfort cost for this edge will be at least \(W_i \times 1 = W_i\).

3. Optimal Coloring Using the Properties of a Tree

To make the total cost as small as possible, the optimal strategy is to have exactly one edge with different colors at its endpoints, and make the difference between those colors the minimum possible value of \(1\).

A tree has an important property: “removing any single edge splits the graph into exactly two connected components (subtrees).”

Using this property, we can color the vertices as follows: 1. Choose any single edge \(e = (u, v)\). 2. Let the two groups formed by removing this edge \(e\) be Group A and Group B. 3. Paint all vertices in Group A with color \(c\). 4. Paint all vertices in Group B with color \(c+1\).

With this coloring, the cost of each edge is as follows: - Edges within Group A: Since both endpoints have color \(c\), the cost is \(0\). - Edges within Group B: Since both endpoints have color \(c+1\), the cost is \(0\). - The unique edge connecting Group A and Group B (the chosen edge \(e\)): Since the endpoint colors are \(c\) and \(c+1\), the cost is \(W_e \times |c - (c+1)| = W_e\).

Since we are using exactly two colors, \(c\) and \(c+1\), this coloring satisfies the problem constraints. The total discomfort cost is exactly \(W_e\).

4. Verification with a Concrete Example

For example, consider a tree (path) with 3 vertices in a line as follows:

[Vertex 1] -- (weight 5) -- [Vertex 2] -- (weight 3) -- [Vertex 3]

• If we choose the edge with weight 3 as the boundary: We paint vertices 1 and 2 with color \(1\), and vertex 3 with color \(2\).

  • Cost of edge (1, 2): \(5 \times |1 - 1| = 0\)
  • Cost of edge (2, 3): \(3 \times |1 - 2| = 3\)
  • Total cost: \(3\)

• If we choose the edge with weight 5 as the boundary: We paint vertex 1 with color \(1\), and vertices 2 and 3 with color \(2\).

  • Cost of edge (1, 2): \(5 \times |1 - 2| = 5\)
  • Cost of edge (2, 3): \(3 \times |2 - 2| = 0\)
  • Total cost: \(5\)

To minimize the cost, we should choose the edge \(e\) with the minimum weight \(W_e\). Therefore, the minimum cost we want to find is simply the minimum value of all edge weights \(W_i\).

---

Algorithm

1. Read the number of edges \(M\) and the weight \(W_i\) of each edge from the input.
2. Find the minimum value among \(W_1, W_2, \ldots, W_M\).
3. Output this minimum value.

Note that vertex information (which vertex is connected to which) does not affect the answer, so it can be safely ignored.

---

Complexity

• Time Complexity: \(O(M)\) Since we only need to check the weight of each edge once, the algorithm runs in linear time with respect to the number of edges \(M\). Since \(M = N - 1 \le 2 \times 10^5\), this easily runs within the time limit.

• Space Complexity: \(O(1)\) Since we can update the minimum value on the fly while reading the input, we do not need to store the entire graph in memory, using almost no extra memory.

---

Implementation Details

• In Python, when processing a large amount of input, using sys.stdin.read().split() allows for fast input reading.

• Since the information of vertices \(u_i, v_i\) is not used to calculate the minimum value, we can skip them and only extract and process the weights \(W_i\).

  Source Code

import sys

def solve():
    # 高速な入出力
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # 各辺の重み W_i の最小値を求める
    min_w = float('inf')
    for i in range(M):
        w = int(input_data[3 + i * 3 + 2])
        if w < min_w:
            min_w = w
            
    print(min_w)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-high.