Задано дерево T, состоящее из n вершин. На каждой вершине записано число; на i-й — ai. Определим функцию I(x, y) — разница между максимальным и минимальным значением ai на простом пути между вершинами x и y.
Ваша задача — вычислить .
В первой строке записано одно целое число n (1 ≤ n ≤ 106) — количество вершин в дереве.
Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 106) — числа, записанные на вершинах.
Затем задана n - 1 строка. В каждой записано по два целых числа x и y, задающие ребро между вершинами x и y (1 ≤ x, y ≤ n, x ≠ y). Гарантируется, что данные ребра формируют дерево.
Выведите одно число — .
4
2 2 3 1
1 2
1 3
1 4
6
Название |
---|