K - Tree Minimization Problem

配点： 点

から までの番号のついた 個の頂点と， 個の辺からなる，連結な重み付き無向グラフがあります．

を満たす任意の整数 について，頂点 と頂点 とを結ぶ，重み の辺が存在します．ただし です．

また，長さ の 正整数列 があり，このとき整数 に対して を次のように定めます：

• 頂点 と頂点 とを結ぶ単純パスに含まれる辺の重みの総和 ．

さらに，任意の重み付きグラフに対して以下の操作を行うことができます：

操作

• 好きな辺を つ選択し，その辺の重みを で置換する．

このグラフに対して，以上の操作を 回以上 回以下行うとき， の値は最小でいくつにすることができますか？
求めてください．

• 入力はすべて整数

各テストケースの入力は，それぞれ以下の形式で与えられる：

答えを出力せよ．

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

39

頂点 を結ぶ辺に対して操作を 回行うことが最適です．

1
2
1 -1
3
1 2
1 2
1 2

-3