No.2115 Making Forest Easy
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 : bayashiko / テスター : QCFium noimi
タグ : / 解いたユーザー数 28
作問者 : bayashiko / テスター : QCFium noimi
問題文最終更新日: 2022-10-13 18:42:31
この問題はH問題の Making Forest Hard と制約および実行時間制限のみが異なります。
問題文
頂点の木 があります。各頂点には から の番号が付けられており、頂点 には整数 が書かれています。
また、 の 本目の辺は頂点 と を結んでいます。
の辺をいくつか選んで削除すると、 は削除した辺の本数を として 個の連結成分 に分かれます。
連結成分 のスコアを、 に含まれる頂点に書かれている整数の最大値を 、 に含まれる頂点の個数を として、 と定めます。
また、辺の削除方法のスコアを、辺の削除によって生じた連結成分たちのスコアの総和と定めます。
辺の削除方法は全部で 通りありますが、その全てに対する辺の削除方法のスコアの総和を で割った余りを求めてください。
入力
:
- 与えられるグラフは木
- 入力はすべて整数
出力
答えを出力してください。
サンプル
サンプル1
入力
3 2 4 6 1 2 1 3
出力
60
どの辺も削除しない場合のスコアは です。
本目の辺だけ削除する場合のスコアは です。
本目の辺だけ削除する場合のスコアは です。
両方の辺を削除する場合のスコアは です。
よって、これらの総和である が答えです。
サンプル2
入力
7 4 2 5 9 10 3 12 1 3 2 3 3 5 3 4 3 7 5 6
出力
4008
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。