No.2949 Product on Tree
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 67
作問者 : nouka28 / テスター : rotti_coder aplysiaSheep t9unkubj
タグ : / 解いたユーザー数 67
作問者 : nouka28 / テスター : rotti_coder aplysiaSheep t9unkubj
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。