← 返回题目列表

Codeforces · 915/F

F. 树的不平衡值

中文机器翻译题面 查看原题

给你一棵由 n 个顶点组成的树 T。每个顶点上都写有一个数字;写在顶点 i 上的数字是 ai。让我们将函数 I(x, y) 表示为连接顶点 x 和 y 的简单路径上 ai 的最大值和最小值之间的差。

您的任务是计算 $$\sum_{i=1}^{n}\sum_{j=i}^{n}I(i,j)$$。

输入

第一行包含一个整数 n (1 ≤ n ≤ 106) — 树中的顶点数。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 106) — 写在顶点上的数字。

接下来是 n - 1 行。每行包含两个整数 x 和 y,表示连接顶点 x 和顶点 y 的边(1 ≤ x,y ≤ n,x ≠ y)。保证这些边代表一棵树。

输出

打印一个等于 $$\sum_{i=1}^{n}\sum_{j=i}^{n}I(i,j)$$ 的数字。

示例

输入 #1

4
2 2 3 1
1 2
1 3
1 4

输出 #1

6