問題一覧 > 通常問題

No.1488 Max Score of the Tree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 133
作問者 : MZKiMZKi / テスター : maguromaguro
11 ProblemId : 6237 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-09 19:13:00

問題文

NN 頂点からなる根付き木 TT が与えられます。TT の頂点には 11 から NN までの番号がついており、根は頂点 11 です。

また、TTN1N-1 本の辺のうち、ii 番目の辺は頂点 aia_i と頂点 bib_i を長さ cic_i で結んでいます。

あなたは TT に対して、以下の操作を 11 回行うことができます。

  • 長さの総和が KK 以下となるように辺を選び、選んだ辺の長さを 22 倍する。

TT のスコアを、葉の深さの総和と定めます。適切に操作を行うことで達成できる、 スコアの最大値を求めてください。

入力

N KN\ K
a1 b1 c1a_1\ b_1\ c_1
a2 b2 c2a_2\ b_2\ c_2
\vdots
aN1 bN1 cN1a_{N-1}\ b_{N-1}\ c_{N-1}

  • 入力は全て整数である。
  • 2N1002 \le N \le 100
  • 1K1051 \le K \le 10^5
  • 1ai,biN1 \le a_i, b_i\le N
  • 1ciK1 \le c_i\le K
  • 与えられるグラフは木である。

出力

達成可能なスコアの最大値を出力し、最後に改行してください。

サンプル

サンプル1
入力
3 7
2 3 4
2 1 5
出力
14

例えば、辺 22 を選べばスコアが 1414 となり、これが最大です。

サンプル2
入力
5 16
2 1 2
5 1 2
4 5 13
3 4 3
出力
36

例えば、辺 33 と辺 44 を選べばスコアが 3636 となり、これが最大です。

サンプル3
入力
16 57
5 12 18
5 13 11
1 12 57
13 10 19
13 3 4
6 1 47
10 2 13
11 12 6
3 14 1
16 1 39
7 5 4
15 2 16
9 5 48
8 13 43
12 4 41
出力
1202

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。