CF915F Imbalance Value of a Tree

给定一棵树，每个顶点都被写上了一个数，第 $i$ 个顶点写上的数是 $a_i$。定义一个函数 $I(x,y)$ 表示从顶点 $x$ 到 $y$ 的简单路径上 $a_i$ 的最大值和最小值的差。 你要求出 $\sum_{i=1}^{n}\sum_{j=i}^{n}I(i,j)$。

第一行一个正整数 $n(1\le n\le 10^6)$，表示树上节点个数。 第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n(1\le a_i\le 10^6)$，表示树上每个节点写的数值。 接下来 $n-1$ 行，每行两个正整数 $x,y$，表示一条边连接节点 $x$ 和 $y$（$1\le x,y\le n$，$x\ne y$）。保证图是一棵树。

输出一个数，表示 $\sum_{i=1}^n\sum_{j=i}^nI(i,j)$。