問題一覧 > 通常問題

No.2115 Making Forest Easy

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 : bayashikobayashiko / テスター : QCFiumQCFium noiminoimi
0 ProblemId : 8400 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-13 18:42:31

この問題はH問題の Making Forest Hard と制約および実行時間制限のみが異なります。

問題文

NN 頂点の木 TT があります。各頂点には 11 から NN の番号が付けられており、頂点 ii には整数 AiA_i が書かれています。

また、 TTii 本目の辺は頂点 uiu_iviv_i を結んでいます。

TT の辺をいくつか選んで削除すると、 TT は削除した辺の本数を kk として k+1k+1 個の連結成分 T1,T2,,Tk+1T'_1,T'_2,\ldots,T'_{k+1} に分かれます。

連結成分 TT' のスコアを、TT' に含まれる頂点に書かれている整数の最大値を MMTT' に含まれる頂点の個数を SS として、M×SM×S と定めます。

また、辺の削除方法のスコアを、辺の削除によって生じた連結成分たちのスコアの総和と定めます。

辺の削除方法は全部で 2N12^{N-1} 通りありますが、その全てに対する辺の削除方法のスコアの総和を 998244353998244353 で割った余りを求めてください。

入力

NN
A1 A2  ANA_1\ A_2\ \ldots\ A_N
u1 v1u_1\ v_1
u2 v2u_2\ v_2
:
uN1 vN1u_{N-1}\ v_{N-1}

  • 2N50002\le N\le 5000
  • 1Ai10001\le A_i\le 1000
  • 1ui,viN1\le u_i,v_i\le N
  • 与えられるグラフは木
  • 入力はすべて整数

出力

答えを出力してください。

サンプル

サンプル1
入力
3
2 4 6
1 2
1 3
出力
60

どの辺も削除しない場合のスコアは 6×3=186×3=18 です。

11 本目の辺だけ削除する場合のスコアは 4×1+6×2=164×1+6×2=16 です。

22 本目の辺だけ削除する場合のスコアは 4×2+6×1=144×2+6×1=14 です。

両方の辺を削除する場合のスコアは 2×1+4×1+6×1=122×1+4×1+6×1=12 です。

よって、これらの総和である 6060 が答えです。

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