G - Fusion Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1600 点

問題文

1 から N までの番号のついた N 頂点からなる木 T があります． i 番目の辺は頂点 A_i と B_i を結んでいます． また，各頂点には整数が書かれており，頂点 i に書かれている整数は V_i です．

あなたは今から以下の操作を N-1 回行います．

  • T の辺を 1 つ選び，縮約する． 縮約前の 2 つの頂点に書かれていた整数を x,y とおき，縮約後の頂点には x \times y+1 を書き込む．

操作を行う方法は (N-1)! 通りあります． 全ての方法について，最終的に残る 1 頂点に書かれた値を求めたとします． これら (N-1)! 個の値の総和を 998244353 で割った余りを求めてください．

辺の縮約とは

グラフ G について，辺 (u,v) を縮約する操作とは，頂点 u,v を 1 つの頂点にまとめる操作です． より正確には，縮約とは G を以下のように変化させる操作です．

  • G から辺 (u,v) および頂点 u,v を削除し，新しい頂点 (これを w と呼ぶ) を追加する．
  • u に接続する各辺 (u,x) を削除し，変わりに辺 (w,x) を追加する．
  • v に接続する各辺 (v,x) を削除し，変わりに辺 (w,x) を追加する．

制約

  • 1 \leq N \leq 5000
  • 1 \leq V_i < 998244353
  • 1 \leq A_i,B_i \leq N
  • 入力されるグラフは木．
  • 入力される値はすべて整数．

入力

入力は以下の形式で標準入力から与えられる．

N
V_1 V_2 \cdots V_N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

出力

答えを出力せよ．

入力例 1

3
1 2 3
1 2
3 2

出力例 1

18

操作を行う方法は以下の 2 通りあります．

  • 最初の操作で辺 (1,2) を選んだ場合，縮約後の頂点には 1 \times 2+1=3 が書き込まれます． 次の操作では，縮約によってできた頂点と頂点 3 を縮約します． すると，3 \times 3+1=10 が書かれた頂点が残ります．
  • 最初の操作で辺 (3,2) を選んだ場合，縮約後の頂点には 3 \times 2+1=7 が書き込まれます． 次の操作では，縮約によってできた頂点と頂点 1 を縮約します． すると，7 \times 1+1=8 が書かれた頂点が残ります．

よって求める答えは 10+8=18 です．

入力例 2

5
1 1 1 1 1
2 1
3 1
4 1
5 3

出力例 2

136

入力例 3

8
3 1 4 1 5 9 2 6
2 1
3 2
4 1
5 2
6 5
7 3
8 7

出力例 3

54388564

入力例 4

20
785439575 250040586 709423541 945005786 19237226 404191280 250876593 22672564 519729087 344065187 273714213 560047126 139793597 542901248 520999410 855572558 498896933 418633758 742973826 248730679
12 9
19 18
9 5
6 20
8 16
3 6
4 14
6 12
16 12
3 17
14 19
15 16
17 13
11 14
17 2
9 7
18 10
19 3
1 18

出力例 4

768399804