regions - 地域 (Regions) Editorial /

Time Limit: 1 sec / Memory Limit: 64 MiB

AtCoder での提出方法

入力は標準入力から読み込み,出力は標準出力に行うこと.

配点 : 100 点

問題文

JOI 国には N 個の都市があり,1 から N の番号がついている.これらの都市は,双方向に通行可能な道でツリー状に接続されている.すなわち,任意の 2 つの都市は道をたどって行き来が可能であり,かつその経路は一意である.このとき,道は N - 1 本である.

都市を,M 個の地域に分けることにした.全ての地域は 1 つ以上の都市を含み,全ての都市はちょうど 1 つの地域に含まれるようにしなければならない.また,同じ地域に含まれる任意の 2 つの都市は,その地域に含まれない都市を通らずに道をたどって行き来が可能でなければならない.

各地域の直径の最大値 d_{max} ができるだけ小さくなるように地域分けをしたい.ある地域の直径とは,その地域に含まれる 2 つの都市間の距離の最大値である.2 つの都市間の距離とは,2 つの都市を結ぶ経路に含まれる道路の長さの和である.地域に 1 つしか都市が含まれない時,その地域の直径は 0 とする.

課題

道の情報と地域の数が与えられると,d_{max} の最小値を計算するプログラムを作成せよ.

制約

  • 2 \leqq N \leqq 30{,}000:都市の数.
  • 2 \leqq M \leqq N:地域の数.
  • 1 \leqq A_i < B_i \leqq N:道 i の結ぶ 2 つの都市.
  • 1 \leqq C_i \leqq 100:道 i の長さ.

入力

標準入力から以下の入力を読み込め.

  • 1 行目には整数 N,M が空白を区切りとして書かれている.
  • 続く N - 1 行には,1 行につき 1 つの道について記述している.これらの行のうちの i 行目は道 i について記述しており,整数 A_{i},B_{i},C_{i} が空白を区切りとして書かれている.

出力

標準出力に d_{max} の最小値を表す 1 つの整数を出力せよ.

採点基準

20 点分のテストグループにおいて,M = 2,N \leqq 1{,}000 である.

40 点分のテストグループにおいて,M = 2 である.

入力例 1

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

出力例 1

3

2 つの地域を都市 1, 4, 5 と都市 2, 3 というようにすれば,d_{max} を 3 にでき,これが最適である.

入力例 2

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

出力例 2

2

3 つの地域を都市 1 と都市 2, 4, 5 と都市 3 というようにすれば,d_{max} を 2 にでき,これが最適である.


Source Name

JOI 2009-2010 春季トレーニング合宿 Contest Day2