题目描述

有一颗 $n$ 个结点的树，结点 $i$ 有权值 $a_i$。

你需要求出这样的点对 $(u,v)$ 的数量：

1、$a_u = a_v$

2、对于 $u$ 到 $v$ 的路径上的任意一个点 $k$， 都有 $a_k \geq a_u$。

点对是无序对，即 $(u,v)$ 和 $(v,u)$ 是同一种。

输入格式

第一行一个正整数 $n$，表示结点数量。

接下来一行 $n$ 个整数 $a_i$，表示结点权值。

接下来 $n - 1$ 行每行两个正整数 $u,v$，表示树上的一条边。

输出格式

一行一个非负整数，表示答案。

7
1 2 1 2 1 2 1
1 2
1 3
2 4
3 5
4 6
4 7

9

样例解释

无

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 3 \times 10^{5},1 \leq u_i \neq v_i \leq n,1 \leq a_i \leq 10^9$。