AT_jsc2023_final_g Fusion

有一棵包含 $N$ 个顶点的树 $T$，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。每个顶点上写有一个整数，顶点 $i$ 上的整数为 $V_i$。 现在你要进行 $N-1$ 次如下操作： - 选择树 $T$ 的一条边，将之进行缩约。假设被缩约的两个顶点上写有的整数分别为 $x,y$，则缩约后新顶点上写入的整数为 $x \times y + 1$。 所有操作顺序的选择方法共有 $(N-1)!$ 种。对所有这种方法，最终剩下的那个顶点上写有的值都求出，并将这 $(N-1)!$ 个值求和后对 $998244353$ 取余，输出所得的余数。 边的缩约指，对于图 $G$，把一条边 $(u,v)$ 进行缩约，等价于将顶点 $u$ 和 $v$ 合并成一个顶点。具体操作如下： - 从 $G$ 删除边 $(u,v)$ 及顶点 $u$、$v$，新增一个新顶点（记作 $w$）。 - 对于 $u$ 的每个相邻顶点 $x$（即边 $(u,x)$），删除 $(u,x)$ 并添加 $(w,x)$。 - 对于 $v$ 的每个相邻顶点 $x$（即边 $(v,x)$），删除 $(v,x)$ 并添加 $(w,x)$。

输入通过标准输入给出，格式如下： > $N$　$V_1$　$V_2$　$\cdots$　$V_N$ > $A_1$　$B_1$ > $A_2$　$B_2$ > $\vdots$ > $A_{N-1}$　$B_{N-1}$

输出答案。

### 样例解释 1 本例有 $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$。 ### 数据范围 - $1 \leq N \leq 5000$ - $1 \leq V_i < 998244353$ - $1 \leq A_i,B_i \leq N$ - 输入保证给出的是一棵树。 - 所有输入均为整数。 由 ChatGPT 5 翻译