外婆与苹果树

小蓝的外婆有一片很大的苹果园，树上的每个节点有且只有一个苹果；每个苹果有唯一一个编号i，每个苹果还有一个重量，用一个整数 $w_{i}$ 表示；

为了度过寒冷的冬天，外婆打算做一些疏果措施，即对差异值过大的果树进行适当的修剪。对于一个果树，我们定义树上从u到v简单路径上所有苹果中最大重量与最小重量的差值为这个路径的差异值(u,v)，一棵树的差异值 $= \sum ^{n-1} _{i=1} \sum ^{n}_{j=i+1}差异值（i，j）$ 。

对于给出的果树，求树的差异值。

第一行一个整数 $T（1\le T \le 10）$ 表示数据组数

对于每组数据：

第一行一个整数 $n（1\le n \le 5×10^{5}，\sum n \le 2×10^{6}）$

第二行n个数字，第i个数字表示编号为i的点的权值 $w_{i},1\le w_{i} \le 10^{9}$ ;

接下来n-1行，每行包含两个数 $u,v，1\le u,v \le n$ ，表示他们之间有一条边相连。

详情