外婆与苹果树

题号：NC219594
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

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

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

输入描述:

第一行一个整数表示数据组数

对于每组数据：

第一行一个整数 

第二行n个数字，第i个数字表示编号为i的点的权值 ;

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

输出描述:

对于每组数据，输出这个树的差异值，由于答案可能很大，请将答案对1e9+7取模之后输出

示例1

输入

复制

1
10
9 9 6 2 4 5 8 5 5 6
2 1
3 1
4 3
5 3
6 4
7 2
8 4
9 5
10 3

输出

复制

备注:

K题