### 问题描述
小明有一棵树,这棵树的每一个顶点都有一个编号,第 i 个顶点的编号是 numi,小红给了小明一个定义:F(x,y) 表示 x 顶点到 y 顶点的简单路径上 ai 的最大值和最小值的差。
简单路径:对于一个有向图或无向图,如果路径上的边和顶点都是互不相同的,那么这条路径就是一个简单路径。
你要计算 ∑ni=1∑nj=1F(x,y)。
第一行,输入一个整数 n,表示树的大小。
第二行,输入 n 个整数,第 i 个整数 numi,表示第 i 个顶点的编号。
接下来 n−1 行,每行两个整数 x,y,表示 x 顶点和 y 顶点有一条边。保证这个图是一棵树。
先输出 Answer:
,然后输出 ∑ni=1∑nj=1F(x,y)。
6
2 3 4 1 5 99
1 2
2 4
1 3
3 5
5 6
Answer:504
对于所有评测数据,1≤n≤106,1≤numi≤106,1≤x,y≤n,x≠y。