配点 : 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