Processing math: 100%
编程题
                ### 问题描述

小明有一棵树,这棵树的每一个顶点都有一个编号,第 i 个顶点的编号是 numi,小红给了小明一个定义:F(x,y) 表示 x 顶点到 y 顶点的简单路径上 ai 的最大值和最小值的差。

简单路径:对于一个有向图或无向图,如果路径上的边和顶点都是互不相同的,那么这条路径就是一个简单路径。

你要计算 ni=1nj=1F(x,y)

输入格式

第一行,输入一个整数 n,表示树的大小。

第二行,输入 n 个整数,第 i 个整数 numi,表示第 i 个顶点的编号。

接下来 n1 行,每行两个整数 x,y,表示 x 顶点和 y 顶点有一条边。保证这个图是一棵树。

输出格式

先输出 Answer:,然后输出 ni=1nj=1F(x,y)

样例输入

6
2 3 4 1 5 99
1 2
2 4
1 3
3 5
5 6

样例输出

Answer:504

评测数据规模

对于所有评测数据,1n106,1numi106,1x,yn,xy

查看答案
赣ICP备20007335号-2