問題一覧 > 通常問題

No.2949 Product on Tree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 76
作問者 : nouka28nouka28 / テスター : rotti_coderrotti_coder aplysiaSheepaplysiaSheep t9unkubjt9unkubj
1 ProblemId : 11081 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-18 06:37:01

問題文

長さ $N$ の非負整数列 $A=(A_1,A_2,\dots,A_N)$ と $N$ 頂点からなる木が与えられます。頂点には $1$ から $N$ の番号がついており、$i$ 番目の辺は頂点 $U_i,V_i$ を結んでいます。

相異なる $2$ 頂点 $i,j$ 間のコスト $f(i,j)$ を次のように定義します。

  • 頂点 $i,j$ を結ぶ単純パス上の頂点を順に $p_1(=i),p_2,\dots,p_k(=j)$ とする。ここで $k$ はパスに含まれる頂点数である。 このとき、 $f(i,j)=A_{p_1}\times A_{p_2} \times \dots \times A_{p_k}$ で定める。

$\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} f(i,j)$ を $998244353$ で割ったあまりを求めてください。

制約

  • $2\leq N\leq 2\times 10^5$
  • $0\leq A_i< 998244353$
  • $1\leq U_i,V_i\leq N$
  • 入力はすべて整数である。
  • 与えられるグラフは木である。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

出力

$\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} f(i,j)$ を $998244353$ で割ったあまりを出力してください。

サンプル

サンプル1
入力
4
1 2 3 4
1 2
2 3
2 4
出力
54

求めるパスは以下の $6$ 通りあります。

  • $f(1,2)=1\times 2=2$
  • $f(1,3)=1\times 2\times 3=6$
  • $f(1,4)=1\times 2\times 4=8$
  • $f(2,3)=2\times 3=6$
  • $f(2,4)=2\times 4=8$
  • $f(3,4)=3\times 2\times 4=24$

求める値は $2+6+8+6+8+24=54$ を $998244353$ で割ったあまりの $54$ です。

サンプル2
入力
2
0 0
1 2
出力
0

サンプル3
入力
10
810284561 609063208 909877398 113848143 744347504 567699714 418423327 541843429 325332295 953873148
10 6
5 10
2 5
4 2
9 6
3 10
8 3
7 10
1 6
出力
318883473

$998244353$ で割ったあまりを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。