Regions(地域) - joi2010-day2
時間制限: 1秒
メモリ制限: 64MB
JOI国にはN個の都市があり, 1からNの番号がついている. これらの都市は, 双方向に通行可能な道でツリー状に接続されている. すなわち, 任意の2つの都市は道をたどって行き来が可能であり, かつその経路は一意である. このとき, 道はN-1本である.
都市を, M個の地域に分けることにした. 全ての地域は1つ以上の都市を含み, 全ての都市はちょうど1つの地域に含まれるようにしなければならない. また, 同じ地域に含まれる任意の2つの都市は, その地域に含まれない都市を通らずに道をたどって行き来が可能でなければならない.
各地域の直径の最大値d[max]ができるだけ小さくなるように地域分けをしたい. ある地域の直径とは, その地域に含まれる2つの都市間の距離の最大値である. 2つの都市間の距離とは, 2つの都市を結ぶ経路に含まれる道路の長さの和である. 地域に1つしか都市が含まれない時, その地域の直径は0とする.
課題(TASK)
道の情報と地域の数が与えられると, d[max]の最小値を計算するプログラムを作成せよ.
制限(CONSTRAINTS)
| 2 ≤ N ≤ 30,000 | 都市の数 |
| 2 ≤ M ≤ N | 地域の数 |
| 1 ≤ A[i] < B[i] ≤ N | 道iの結ぶ2つの都市 |
| 1 ≤ C[i] ≤ 100 | 道iの長さ |
入力(INPUT)
標準入力から以下の入力を読み込め.
- 1行目には整数N,Mが空白を区切りとして書かれている.
- 続くN-1行には, 1行につき1つの道について記述している. これらの行のうちのi行目は道iについて記述しており, 整数A[i],B[i],C[i]が空白を区切りとして書かれている.
出力(OUTPUT)
標準出力にd[max]の最小値を表す1つの整数を出力せよ.
採点基準(GRADING)
20点分のテストグループにおいて, M = 2, N ≤ 1,000 である.
40点分のテストグループにおいて, M = 2 である.
入出力例(EXAMPLE)
| 入力例(Sample Input) | 出力例(Sample Output) |
|---|---|
| 5 2 1 4 2 2 3 3 2 4 1 4 5 1 |
3 |
2つの地域を都市1,4,5と都市2,3というようにすれば, d[max]を3にでき, これが最適である.
| 入力例(Sample Input) | 出力例(Sample Output) |
|---|---|
| 5 3 1 4 2 2 3 3 2 4 1 4 5 1 |
2 |
3つの地域を都市1と都市2,4,5と都市3というようにすれば, d[max]を2にでき, これが最適である.