問題一覧 > 通常問題

No.2116 Making Forest Hard

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

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

問題文

$N$ 頂点の木 $T$ があります。各頂点には $1$ から $N$ の番号が付けられており、頂点 $i$ には整数 $A_i$ が書かれています。

また、 $T$ の $i$ 本目の辺は頂点 $u_i$ と $v_i$ を結んでいます。

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

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

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

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

入力

$N$
$A_1\ A_2\ \ldots\ A_N$
$u_1\ v_1$
$u_2\ v_2$
:
$u_{N-1}\ v_{N-1}$

  • $2\le N\le 10^5$
  • $1\le A_i\le 998244352$
  • $1\le u_i,v_i\le N$
  • 与えられるグラフは木
  • 入力はすべて整数

出力

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

サンプル

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

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

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

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

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

よって、これらの総和である $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もしくは右上の雲マークをクリックしてアカウントを作成してください。