No.1488 Max Score of the Tree
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 133
作問者 :
MZKi
/ テスター :
maguro
タグ : / 解いたユーザー数 133
作問者 :
![MZKi](https://pbs.twimg.com/profile_images/1156206593903493120/QF23VwZE.jpg)
![maguro](https://pbs.twimg.com/profile_images/1377558870600470534/3rZWsjr_.jpg)
問題文最終更新日: 2023-03-09 19:13:00
問題文
頂点からなる根付き木 が与えられます。 の頂点には から までの番号がついており、根は頂点 です。
また、 の 本の辺のうち、 番目の辺は頂点 と頂点 を長さ で結んでいます。
あなたは に対して、以下の操作を 回行うことができます。
- 長さの総和が 以下となるように辺を選び、選んだ辺の長さを 倍する。
のスコアを、葉の深さの総和と定めます。適切に操作を行うことで達成できる、 スコアの最大値を求めてください。
入力
- 入力は全て整数である。
- 与えられるグラフは木である。
出力
達成可能なスコアの最大値を出力し、最後に改行してください。
サンプル
サンプル1
入力
3 7 2 3 4 2 1 5
出力
14
例えば、辺 を選べばスコアが となり、これが最大です。
サンプル2
入力
5 16 2 1 2 5 1 2 4 5 13 3 4 3
出力
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もしくは右上の雲マークをクリックしてアカウントを作成してください。