問題一覧 > 通常問題

No.1488 Max Score of the Tree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 101
作問者 : MZKiMZKi / テスター : maguromaguro
9 ProblemId : 6237 / 出題時の順位表
問題文最終更新日: 2021-04-06 15:11:54

問題文

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

また、$T$ の $N-1$ 本の辺のうち、$i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を長さ $c_i$ で結んでいます。

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

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

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

入力

$N\ K$
$a_1\ b_1\ c_1$
$a_2\ b_2\ c_2$
$\vdots$
$a_{N-1}\ b_{N-1}\ c_{N-1}$

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

出力

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

サンプル

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

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

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

例えば、辺 $3$ と辺 $4$ を選べばスコアが $36$ となり、これが最大です。

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。