AT_jsc2023_final_g.Fusion

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一棵包含 $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
```
3
1 2 3
1 2
3 2
```
输出#1
```
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

说明/提示

样例解释 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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页