H - High-powered Illuminations
解説
/
実行時間制限: 3 sec / メモリ制限: 256 MB
配点 : 100 点
問題文
うさぎはクリスマスに向けてクリスマスツリーを用意した.
賢明なる参加者諸氏はお気づきかもしれないが,クリスマスツリーとはもちろんグラフ理論における木構造のことである.ツリーは N 個の頂点 (頂点 1,\ 2,\ ...,\ N) からなり,N-1 本の辺を持つ.i (1 \leq i \leq N-1) 本目の辺は頂点 A_i と頂点 B_i を結ぶ長さ C_i の辺である.
うさぎは K 個の電球を持っており,それぞれの電球をツリーの頂点に置いて飾りつけようとしている.しかし,うさぎの持っている電球は非常に光量が大きいため,あまり電球どうしが近くなるとツリーが眩しくなりすぎてしまう.そこでうさぎは,電球どうしの距離をできるだけ遠ざけて電球を配置することにした.ここで,電球どうしの距離とは,電球が設置された頂点どうしの距離である.2 つの頂点間の距離は,片方の頂点からもう一方の頂点へツリーの辺を辿って行くときに,辿る辺の長さの和の最小値である.
N 個の頂点のうち K 個に電球を置いて光らせるとき,電球どうしの距離の最小値 d を考える.d として考えられる値のの最大値を求めよ.
制約
- 2 \leq K \leq N \leq 200,000.
- 1 \leq A_i, B_i \leq N.
- 1 \leq C_i \leq 5,000.
- A_i \neq B_i.
- 入力は木構造を表していることが保証される.
部分点
- N \leq 40,000 であるようなデータセットに正解した場合は,50 点が与えられる.
- 追加制約のないデータセットに正解した場合は,上記とは別に 50 点が与えられる.
入力
入力は以下の形式で標準入力から与えられる.
N K A_1 B_1 C_1 A_2 B_2 C_2 : A_{N-1} B_{N-1} C_{N-1}
出力
電球どうしの距離の最小値 d として考えられる値の最大値を 1 行に出力せよ.
入力例 1
4 3 2 1 100 3 2 200 4 2 300
出力例 1
300
頂点 1,\ 3,\ 4 に飾れば良い.
入力例 2
9 4 1 2 1 1 3 1 3 4 1 1 5 1 6 5 1 7 5 1 8 5 1 9 8 1
出力例 2
3
頂点 2,\ 4,\ 6,\ 9 に飾れば良い.
入力例 3
6 2 1 2 20 1 3 16 1 4 1224 4 5 1400 4 6 1700
出力例 3
3100
入力例 4
12 4 4 8 1214 12 7 890 3 1 651 5 9 1990 1 2 1671 4 1 55 6 4 761 7 2 862 11 10 1469 11 7 1122 12 9 364
出力例 4
2940