A11501 | $Imbalance Value of a Tree$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

You are given a tree $T$ consisting of $n$ vertices. A number is written on each vertex; the number written on vertex $i$ is $a_{i}$ . Let's denote the function $I(x,y)$ as the difference between maximum and minimum value of $a_{i}$ on a simple path connecting vertices $x$ and $y$ . Your task is to calculate ![](/uploads/acgo/image/de36af0cd6f32594_6c8b5039626f.jpeg).

The first line contains one integer number $n$ ( $1<=n<=10^{6}$ ) — the number of vertices in the tree. The second line contains $n$ integer numbers $a_{1}$ , $a_{2}$ , ..., $a_{n}$ ( $1<=a_{i}<=10^{6}$ ) — the numbers written on the vertices. Then $n-1$ lines follow. Each line contains two integers $x$ and $y$ denoting an edge connecting vertex $x$ and vertex $y$ ( $1<=x,y<=n$ , $x≠y$ ). It is guaranteed that these edges denote a tree.

Print one number equal to ![](/uploads/acgo/image/de1e9cf9f6a911af_bd968f121493.jpeg).

输入 #1

输出 #1

C++ 编辑器

输入

输出