E-牛牛选路径_牛客练习赛93

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛有一张无向连通图，图上有 $n$ 个点和 $m$ 条边，每个点有一个权值 $a_i$ 。

现在牛牛想选出最少的路径（一条路径可以重复覆盖同一条边），使得每条边被覆盖奇数次，并且使这些路径权值和最小。

一条路径的权值定义为：路径两端节点的点权之积。

他现在想知道最小的权值和。

第一行，输入两个正整数 ，表示图的规格。

第二行，输入  个正整数 ，表示点  的权值。

接下来  行，每行两个正整数 ，表示  和  之间连有一条边。

对于  的数据，，， ,且数据保证是一个连通图。

一个正整数，表示最小的路径权值和。(答案对998244353取模)

示例1

复制

5 7
83 49 41 75 92 
1 5
1 3
5 4
1 2
2 5
4 3
1 3

复制

一种可行的办法，一条路径为3->1->5->2->1->3->4->5，所以路径的权值是41*92