时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
卡特莉正在爬树，此时她又在树梢发现了一个谜题，为了不令她分心以至于发生意外，请你帮她解决这个问题。
具体地来说,我们定义树上从u到v简单路径上所有点权中最大值与最小值的差值为这条路径的"平衡值"，记为balance(u,v)。
一棵树的)
具体地来说,我们定义树上从u到v简单路径上所有点权中最大值与最小值的差值为这条路径的"平衡值"，记为balance(u,v)。
一棵树的
输入描述:
第一行输入一个T(1<=T<=10)表示数据组数。
接下来T组数据。
对于每组数据，第一行输入一个n(1<=n<=500000)。保证n的总和不大于2000000
然后接下来一行输入n个数字，第i个数字表示标号为i的点的权值(
)。
然后输入n-1行，每行包含两个数u、v，表示一条边连接u与v。
保证输入n-1条边将标号1至标号n组成一棵树。
输出描述:
对于每组数据，请你输出一个数表示输入的树的BALANCE值，由于答案可能很大，请将答案对1000000007取模后输出。
请注意行末不要输出多余空格。