解题思路

先考虑相邻两个节点之间的限制：

• 如果 $freq[u] < freq[v]$，那么节点 $v$ 的水晶数必须严格大于节点 $u$
• 如果 $freq[u] = freq[v]$，那么这条边没有大小限制
• 如果 $freq[u] > freq[v]$，结论同理

于是可以把问题转化为：

题目内容

多多家里生长着一棵巨大的魔法树。这裸树由 $n$ 个魔法节点组成，节点之间通过 $n-1$ 条能量脉络相连(保证整体是一棵无向连通树)

每个魔法节点都有一个“共鸣频率"，用一个整数数组 $freq$ 表示。为了维持魔法树的运转，你需要给每个节点分配能量水晶。分配规则如下:

• 每个魔法节点至少需要被分配 $1$ 颗能量水晶。

• 对于任何通过能量脉络直接相连的两个节点，共鸣频率更高的节点，必须获得比另一节点严格更多的能量水晶。

• 如果直接相连的两个节点共鸣频率相同，它们之间的水晶数量没有任何约束。

请你计算并返回，为了维持魔法树的运转，最少需要准备多少颗能量水晶？

输入描述

第一行包含一个整数 $n(1<=n<=100,000)$，表示魔法节点的数量。节点编号从 $0$ 到 $n-1$。

第二行包含 $n$ 个整数，第 $i$ 个整数表示 $freq[i](1<=freq[i]<=1000,000,000)$。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ ，表示节点 $u$ 和节点 $v$ 之间有一条能量脉络直接相连。

输出描述

返回一个整数，表示最少需要的能量水晶总数。

补充说明

对于 $60$% 的数据，$n<=1000$;

对于 $100$% 的数据，$n<=100,000$;

样例1

输入

4
1 3 2 4
0 1
1 2
2 3

输出

6

说明

该树为一条直线:$0(1)-1(3)-2(2)-3(4)$

节点 $0$：$1$ 颗

节点 $2$：$1$ 颗

节点 $1$ (连着 $0$ 和 $2$，频率最高)：需要比节点 $0$ 和 $2$ 都多，分配 $2$ 颗

节点 $3$ (连着 $2$ ，频率比 $2$ 高)：分配 $2$ 颗

总计：$1+2+1+2=6$。

样例2

输入

5
5 1 1 1 1
0 1
0 2
0 3
0 4

输出

6

说明

节点 $0$ 位于中心，频率为 $5$。周围 $4$ 个叶子节点频率为 $1$。

$4$ 个叶子节点各分配 $1$ 颗水晶。

中心节点 $0$ 频率高于所有相连节点，必须比它们都多，分配 $2$ 颗。

总计 $1*4+2=6$ 颗。