E-牛客推荐系统开发之标签重复度

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

题目描述

牛客讨论区的每一篇帖子都会有一些标签，比如说“编程语言”、“秋招”、“招聘”等。有些标签是其他标签的子标签，比如“秋招”是“招聘”的子标签。于是这种父子标签的关系可以用一棵树来表示，即某个标签一定是另一个标签的子标签或者这个标签是这棵树的树根节点，每一个标签都有一个权值 $w_i$ 。

定义两个的标签的重复度（这两个标签可以是相同的）为这在这棵树上这两个标签组成的简单路径中的最大权值乘以最小权值。

定义一棵标签树的标签重复度为这棵树上每两个标签之间的重复度之和。

你作为优秀的牛客算法工程师，需要去求某一棵有 ${n}$ 个标签的标签树的重复度，求出答案对998244353取模后的结果即可。

第1行为一个整数，表示总共有个标签；
第2行为n个整数，即，表示第个标签的权值；
接下来n-1行，每行两个整数，表示标签和标签互为父子标签关系。

一个整数，为所求答案模998244353后的结果。

示例1

复制

5
9 12 18 10 15
5 3
3 1
3 2
2 4

复制

示例2

复制

1
1

复制