UOJ Logo

NOI.AC

1S 512MB

#240. tree

Statistics

【题目描述】

给一棵 $n$ 个点的无根树,每个点有一个点权,一条路径的权值定义为路径上点权的最大值乘上最小值。求所有路径的权值之和。两条路径不同当且仅当这两条路径所包含的点集不同。

【输入格式】

第一行一个整数 $n$,第二行有 $n$ 个正整数,$a_1,a_2,...,a_n$,表示每个点的点权。接下来 $n − 1$ 行,每行两个整数 $u$,$v$ 表示树上的一条边。

【输出格式】

共一行,为所有路径的权值之和,答案对 $998244353$ 取模。

【样例 1 输入】

3
1 2 3
1 2
1 3

【样例 1 输出】

22

【数据范围】

对于 $30%$ 的数据,$n \leq 100$

对于 $100%$ 的数据,$n \leq 1000,a_i \leq 5000$