← 返回题目列表

AtCoder · jsc2023_final_g

G. 融合

中文机器翻译题面 查看原题

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