E - 地図の塗り分け 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は、ある地域の地図を塗り分ける仕事を任されました。

地図は N 個の区画に分かれており、それぞれの区画にちょうど 1 つの色を塗る必要があります。使える色は K 種類あり、色 1, 色 2, \ldots, 色 K と番号が付けられています。各区画には 1 以上 K 以下の整数（色番号）を 1 つ割り当てます。この色番号は単なるラベルではなく、番号の大小関係が違和感コストの計算に直接用いられます。

区画同士の隣接関係は M 組与えられます。隣接関係を辺とみなすと、区画を頂点としたグラフは木構造をなします（すなわち M = N - 1 であり、グラフは連結です）。i 番目 (1 \leq i \leq M) の隣接関係は区画 u_i と区画 v_i の間にあり、その境界には重み W_i が定められています。区画 u_i に色番号 a を、区画 v_i に色番号 b を割り当てたとき、その境界における違和感コストは W_i \times |a - b| と定義されます。

高橋君は、すべての区画に色を塗ったとき、すべての境界における違和感コストの合計をできるだけ小さくしたいと考えています。ただし、以下の制約があります：

  • 2 種類以上の色を使わなければなりません。すなわち、すべての区画にまったく同じ色番号を割り当てることは許されません。（隣接する区画同士に同じ色番号を割り当てること自体は許されます。）

すべての区画への色の割り当て方のうち、上記の条件を満たしつつ違和感コストの合計が最小となるものを求め、その最小コストを出力してください。

N \geq 2 かつ K \geq 2 であるため、条件を満たす割り当て方は必ず存在することが保証されます。

制約

  • 2 \leq N \leq 2 \times 10^5
  • M = N - 1（すなわち、隣接関係は木構造をなす）
  • 2 \leq K \leq 10^8
  • 1 \leq u_i < v_i \leq N
  • 1 \leq W_i \leq 10^5
  • 隣接関係に重複はない（同じ区画の組が 2 回以上現れない）
  • 与えられるグラフは連結である
  • 入力はすべて整数である

入力

N M K
u_1 v_1 W_1
u_2 v_2 W_2
\vdots
u_M v_M W_M
  • 1 行目には、区画の数 N、隣接関係の数 M、使える色の種類数 K が、スペース区切りで与えられる。制約より M = N - 1 が保証される。
  • 続く M 行のうち i 行目 (1 \leq i \leq M) には、区画 u_i と区画 v_i が隣接していることと、その境界の重み W_i が、スペース区切りで与えられる。

出力

2 種類以上の色を使うという条件のもとでの、違和感コストの合計の最小値を 1 行で出力せよ。

入力例 1

4 3 3
1 2 5
2 3 2
2 4 8

出力例 1

2

入力例 2

3 2 2
1 2 4
2 3 7

出力例 2

4

入力例 3

10 9 5
1 2 3
2 3 7
3 4 2
1 5 9
5 6 4
6 7 6
4 8 5
8 9 1
9 10 8

出力例 3

1

入力例 4

20 19 1000
1 2 100
2 3 200
3 4 150
4 5 300
5 6 250
6 7 400
7 8 350
8 9 500
9 10 450
10 11 600
11 12 550
12 13 700
13 14 650
14 15 800
15 16 750
16 17 900
17 18 850
18 19 950
19 20 50

出力例 4

50

入力例 5

2 1 2
1 2 1

出力例 5

1

Score : 466 pts

Problem Statement

Takahashi has been assigned the task of coloring a map of a certain region.

The map is divided into N districts, and each district must be colored with exactly one color. There are K available colors, numbered 1, 2, \ldots, K. Each district is assigned an integer (color ID) from 1 to K inclusive. These color IDs are not just labels; their numerical differences are directly used to calculate the discomfort cost.

There are M pairs of adjacent districts. If we view the adjacency relations as edges, the graph with districts as vertices forms a tree structure (that is, M = N - 1 and the graph is connected). The i-th (1 \leq i \leq M) adjacency relation is between district u_i and district v_i, and their boundary has a weight W_i. When district u_i is assigned color a and district v_i is assigned color b, the discomfort cost at their boundary is defined as W_i \times |a - b|.

Takahashi wants to minimize the sum of discomfort costs over all boundaries when all districts are colored. However, there is the following constraint:

  • At least 2 different colors must be used. That is, it is not allowed to assign the exact same color to all districts. (Assigning the same color to adjacent districts is allowed.)

Find the minimum total discomfort cost among all valid color assignments, and output this minimum cost.

Since N \geq 2 and K \geq 2, it is guaranteed that a valid assignment always exists.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • M = N - 1 (that is, the adjacency relations form a tree structure)
  • 2 \leq K \leq 10^8
  • 1 \leq u_i < v_i \leq N
  • 1 \leq W_i \leq 10^5
  • There are no duplicate adjacency relations (the same pair of districts does not appear more than once).
  • The given graph is connected.
  • All input values are integers.

Input

N M K
u_1 v_1 W_1
u_2 v_2 W_2
\vdots
u_M v_M W_M
  • The first line contains the number of districts N, the number of adjacency relations M, and the number of available colors K, separated by spaces. The constraints guarantee M = N - 1.
  • The i-th of the following M lines (1 \leq i \leq M) contains the adjacent districts u_i and v_i, and the weight of their boundary W_i, separated by spaces.

Output

Print the minimum total discomfort cost under the condition that at least 2 different colors are used, in a single line.

Sample Input 1

4 3 3
1 2 5
2 3 2
2 4 8

Sample Output 1

2

Sample Input 2

3 2 2
1 2 4
2 3 7

Sample Output 2

4

Sample Input 3

10 9 5
1 2 3
2 3 7
3 4 2
1 5 9
5 6 4
6 7 6
4 8 5
8 9 1
9 10 8

Sample Output 3

1

Sample Input 4

20 19 1000
1 2 100
2 3 200
3 4 150
4 5 300
5 6 250
6 7 400
7 8 350
8 9 500
9 10 450
10 11 600
11 12 550
12 13 700
13 14 650
14 15 800
15 16 750
16 17 900
17 18 850
18 19 950
19 20 50

Sample Output 4

50

Sample Input 5

2 1 2
1 2 1

Sample Output 5

1