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$,表示树上每个节点写的数值。 接下来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)$

题目描述

You are given a tree $ T $ consisting of $ n $ vertices. A number is written on each vertex; the number written on vertex $ i $ is $ a_{i} $ . Let's denote the function $ I(x,y) $ as the difference between maximum and minimum value of $ a_{i} $ on a simple path connecting vertices $ x $ and $ y $ . Your task is to calculate .

输入输出格式

输入格式

The first line contains one integer number $ n $ ( $ 1<=n<=10^{6} $ ) — the number of vertices in the tree. The second line contains $ n $ integer numbers $ a_{1} $ , $ a_{2} $ , ..., $ a_{n} $ ( $ 1<=a_{i}<=10^{6} $ ) — the numbers written on the vertices. Then $ n-1 $ lines follow. Each line contains two integers $ x $ and $ y $ denoting an edge connecting vertex $ x $ and vertex $ y $ ( $ 1<=x,y<=n $ , $ x≠y $ ). It is guaranteed that these edges denote a tree.

输出格式

Print one number equal to .

输入输出样例

输入样例 #1

4
2 2 3 1
1 2
1 3
1 4

输出样例 #1

6